I think that most people are over concerned with the Windows registry. Problem is, most people shouldn't open that door. Most "registry cleaners" are going to do nothing but damage programs or your Windows Operating System itself. You might not even notice it at first but then when you go to run a program you get the dreaded ERROR message. Most likely it came from deleting registry keys/values/etc.
I have to admit that I opened that door on many occasion myself, hunting down every little reference to a program that I uninstalled.
Your right about exporting/importing the entire registry itself, if you don't "roll back" the registry before you install anything else, the new program is doomed to fail.
Revo uninstaller is an excellent application when uninstalling, it enables you to check off what you want or don't want to delete & will even delete to the recycle bin in case your unsure if you should have deleted the entry. To top it off, it will create a restore point before uninstalling just for those catastrophic failure moments.
You'll hear conflicting stories on whether or not to "clean" the Windows registry, in my opinion, don't ever use a registry cleaner. If you need a program to sweep out your registry you shouldn't be cleaning it in the first place. I understand the desire to have a "clean" registry, so after I uninstall a program i do a regedit & manual search for the program name & installer, deleting what is left over.
As far as any programs go, after doing a manual registry search I use a program called "Everything". It's kind of a Windows Explorer replacement except EXTREMELY fast. It tends to find things in places I would have never thought to look, like "AppData\Roaming".
The only other I would suggest is Windows Live One Care