Sinceramente, todo lo que puedas llegar a hacer dentro del sistema operativo, como pasarle el CCleaner, son simples «parches» que no solucionan nada. Lo mejor es darle formato. Puedes hacerlo de la manera simple, con algún disco de recuperación que te hayas hecho, o de modo «manual» (recomendado), pero para este último sí necesitas respaldar tus archivos. Ya sé que formatear una compu da muchísima flojera, pero ni es tanto tiempo, y cuando queda lista generalmente vale mucho la pena. Es lo mejor que puedes hacer.
Adicionalmente, hay un programa llamado TuneUp Utilities; yo tengo años usándolo, me mantiene la compu en perfecto estado, pero hay que correrlo constantemente. Me imagino que puede hacer «algo» por tu compu, pero yo no esperaría el mismo resultado que un formato. El programa es de pago, pero puedes descargar una versión de prueba por 30 días (vale la pena comprarlo). Lo corres y aplicas todos los análisis y optimizaciones, y ¡voilá!
De aquí lo descargas:
http://www.tuneup.es/
Edito: Ya deberías pensar en actualizarte a Windows 10
Que no te permita restaurar el sistema a un punto anterior (cosa que no te serviría para nada) indica que el sistema operativo se encuentra corrupto o dañado. Ponle atención a tu maquina.