I just come across this thread and I ever messed up by registry cleaner. Maybe you might like to try freeware like Iobit unistaller instead of using add/remove program in control panel. The freeware provide powerful scan option to delete file and registry.
Usually , it rarely needs to reboot after uninstallation yet for some software , reboot might be required.
This might not help on uninstalled program as your preference yet you might consider using it for the next uninstallation.
For the software that has been uninstalled , if you provide the name of application, there might be somebody help you out. Also, some software vender may provide specific tool or method for such software uninstallation.
just one another opinion.