I continue to bang the old drum - "you don't gain anything much by using any registry cleaners but you stand to lose a hell of a lot".
OK that isn't totally true. I do poke around in my registry and delete things I know don't need to be there but almost all reg cleaners are designed to maximise the number of items that can be hit (so they look impressive) and don't focus on the items that should be hit. The other big problem I have found in the past (and it is still true today) - if you have any version of MS Office installed there are hundreds of registry entries that reg cleaners want to remove from a fresh install - if you allow it to happen then somewhere down the road there will be trouble.
The same goes for windows itself - try doing a clean install of windows in a virtual machine and then run a registry cleaner - there are hundreds of entries to be deleted before you have done anything at all. I know MS aren't prefect but it is a little far fetched that all of these entries should be removed on a clean, fresh installation.
IMHO if a registry entry is no longer valid (i.e. something has been left behind following an uninstall) then chances are that no application is ever going to look at that key again. It might give a warm glow to know you have deleted the key but it will not make any practical difference to your system in terms of speed or registry size.
Comparisons I read also showed that defragging your registry has almost no impact on speed (but can cause problems with in use entries getting lost or corrupted in the process).
My poultry reference above was actually not so much to do with registry cleaning in Perfect Utilities but some of the other system cleaning tools. I am fairly happy letting CCleaner delete a load of stuff because experience tells me that so long as you select carefully what is deleted it doesn't seem to do any damage. Other file cleaning tools I have tried have not been quite so conservative!