El mismo CCleaner tiene una utilidad que permite quitar de la lista de programas instalados. Intenta quitarlo de la lista y luego haz una limpieza del registro.

Pues alguna entrada del resgitro debe quedar por algun lado. Te recomiendo el Registry life ( http://registry-life.softonic.com/ ) que es gratuito y muy bueno

Cuando desinstalas Firefox te pregunta si quieres eliminar todas las preferencias de usuario, si escoges "no" el navegador deja "rastros" como la carpeta de Cache, Historial, etc. que me imagino CCleaner detecta y por eso te aparece. En todo caso no es gran problema ni afecta para nada el rendimiento del programa, ni de Windows, así lo he visto pues a mi me pasa lo mismo pero con Opera.

Elimina los registros que deja, con eso NO vuelve a aparecer

marina 57 - Ya lo hice desde regedit, busque y elimine todas las entradas de Mozilla y de Firefox, volvi a instalar el ccleaner y jajaja!! lo mismo...