I feel your pain. But the slow down may not be caused solely or even primarily by the registry.
First, before you get into cleaning your registry, which probably needs a cleaning, make sure you delete temporary files. I had a client with 5,000 temp files slowing down his computer including over 700 in the root directory (c:\). Never allow that many files in your root directory -- it will bring the computer to a near halt.
Second, a number of security programs do slow down computers. Norton is the worst offender, although Trend Micro Pc-Cillan and McAfee are also culprits. Kaspersky Internet Security 7 does not slow down your computer at all. You can get a free 30-day trial from http://usa.kaspersky.com/ -- great tech support based in the USA.
Third, when was the last time your defragmented your hard drive? You should defrag monthly if not more often depending on use. Windows' built-in defrager works, but oh so slowly. Diskeeper is a gem -- it works in the background with no affect on computer speed. You can get a free 30-day trial from http://www.diskeeper.com .
As for registry cleaners, I think I've tried them all. There are a slew of registry repair utilities out there. I've come to conclude that you get what you pay for. I've settled on Registry Booster 2 for all of our computers -- it does the most thorough job without going too far. Available at: http://www.liutilities.com/products/registrybooster
It's not free, but it has more than paid for itself many times over.
I know lots of technical writers like JV PowerTools which is very powerful - perhaps too powerful. I frequently had to restore registry edits it made because it regularly broke programs.
System Mechanic's registry repair utility is child's play, nearly useless.
I'm sure there are a number of other good registry repair utilities out there that will be mentioned in this thread. Just make sure that whatever you use, that it has a restore feature so you can restore registry repairs that break programs. It is likely that you'll run into that problem one time or another (although I must admit I haven't run into it yet with Registry Booster2 on 4 Windows XP computers.)