Bezüglich "CCleaner" und anderen Tools zum "Säubern " der Registry:
Microsoft does not support the use of registry cleaners.
Übersetzt etwa:
Microsoft betreut keinen Einsatz von Registry Cleanern.
http://support.microsoft.com/kb/2563254
Das mindeste, was man vor dem Rummfummeln machen sollte, wäre einen Systemwiederherstellungspunkt zu setzen.
Dazu geht man wie folgt vor:
1) Windowstaste und Pause/Untbr (in der Regel ganz rechts oben) gleichzeitig drücken.
2) Links auf "Computerschutz" klicken.
3) das Systemlaufwerk auswählen/anklicken und prüfen, ob der Schutz auf "Ein" steht. Falls nein, auf "Konfigurieren..." klicken und "Computerschutz" aktivieren auswählen.
4) auf "Erstellen..." klicken
Und nun müsste man nur noch zusehen, dass man im schlimmsten Notfall davon booten könnte.
Wenn also keine passende DVD/ISO vorhanden ist, kann man sich wenigstens einen Reperatur-Datenträger erstellen:
http://www.deskmodder.de/wiki/index.php?title=Reparatur_Wiederherstellung_Windows_8.1#Wiederherstellungslaufwerk_erstellen_Windows_8.1
Oder man bricht den Startvorgang mindestens drei mal ab, dann sollte man auch in dem Reperaturmodus kommen.
Die weitere Vorgehensweise und alternative Wiederherstellungs-/Sicherungsmöglichkeiten stehen im vorherigen Link.
Zum eigentlichen Thema: Bevor man an der Registry rummfummelt, würde ich es zunächst entweder mit einer Systemwiederherstellung/Image Backup (falls vorhanden) oder mit einer Neuinstallation des betroffenen Programms versuchen.
Erst wenn das nicht hilft, würde ich die Registry
manuell in der regedit.exe über "Bearbeiten" => "Suchen" (Strg+F) nach den Einträgen für das Programm suchen und mit "Weitersuchen" (F3) alle weiteren Reste suchen und löschen lassen.
edit: Und im Anschluss natürlich das Programm neuinstallieren.