No uséis el CCleaner para Windows más actuales que el XP, está programado bajo la API Win32, y, lamentablemente, no soporta todo tipo de cadenas y entradas nuevas en los registros de Win7 - 8, por lo que internamente las da como inválidas y las elimina, aunque el CCleaner no se de cuenta de ello (un "fallo de la API, no del programa).
Yo usaría algún otro, aunque realmente no hace falta, el sistema no se va a relantizar porque 4 entradas se queden huérfanas al desinstalar algún programa, sí que iría lento si tuviera muchas entradas al registro erróneas o que faltaran y demás.
Personalmente, tareas de mantenimiento como borrar caché, temporales, iconos y demás bien, pero para cosas tan delicadas como el registro, salvo que no sea algún programa especialista en ésto (y ni me confiaría mucho) mejor no tocar, Windows ya está al tanto de estas cosas y sus soluciones y optimizaciones tiene.