Miałem podobny problem.Poradziłem sobie:
Uruchom egeditedycjaznajdź...tam wpisałem nazwe programu i ręcznie usuwałem klucze,wartości ,dane tego programu.Było tego sporo i dotąd usuwałem aź miałem komunikat źe wyszukiwanie zostało zakończone.
Pomogło.Mogłem zainstalować ponownie program bez problemu.Dla bezpieczeństwa naleźy zrobić kopie rejestru.A tak na marginesie to uźywaj do deinstalacji programów oryginalnych deinstalatorów.
Prawdopodobnie twoj problem polega na tym,źe usunięto program funkcją "usuń" do kosza...

To o co chodzi ?? Boli Cie ze masz w dodaj/usun wpis od gry ktorej nie masz czy chcesz zainstalować gre a instalator odpowiada ze juz jest zainstalowana ??
Jak usunac sama pozycje z dodaj/usun przeciez podlinkował Ci gusioo

To nic nie daje. Nawet RegCleaner. Po prostu chce zainstalować Gothica: Noc Kruka , ale najpierw muszę mieć Gothica 2.
Faktem jest, źe kiedyś miałęm juź zainstalowanego G2 ale gdy go usunąłęm został mi w Dodaj lub Usuń wpis, źe G2 jest zainstalowany i ma 15 MB. Jak to usunąć.???

Odpowiedź brzmi:
http://www.centrumxp.pl/forum/viewtopic.php?t=30157