Hola, haz lo que te dice fpardo, pero quiero aconsejarte si me lo permites.
Dices "le pasé el CCleaner y otros software que borran las navegaciones"
ccleaner y otros softwares te estan dañando a windows y vete a saber que le hace al navegador.
Puede ser esa la causa, el utilizar limpiadores.
Windows ya tiene su limpiador, el liberador de espacio.
Te dejo enlaces de ayuda, son ejemplos del daño que hacen.
Saludos.