Regardless of what the program is if I uninstall it (for good) I follow that up with a registry clean to ensure all traces are gone.
I have just done this with firefox 1.5 as I was having issues that I believe were related to NoScript stopping extension updates and/or installation. Nothing I did could resolve the problem and a simple uninstall doesn't get rid of everything, you have to delete the program folder and profile and any registry entries to be thoroughly clear.
Once reinstalled things are working as they should be with the exception I haven't installed the NoScript extension.
So if this applies to ordinary software which really isn't trying to hide, what would spyware leave behind.
A registry cleaner for the most part is fine depending on the one you choose some are very cautious some are very aggressive in what they flag and if you know little about the registry, then you could have problems especially if that cleaner doesn't have a backup/recovery function.