I have tried a few of these, and all in all, I can say they have helped me out a great deal. The one I have decided to stay with is Auslogics Boostspeed (a suite of utilities, including regcleaner).
One example is boot-speed. I count how many times the slider under the Windows-logo go across the screen to see if I get an improvement. I downloaded the trial and searched the registry. At that time, the slider ran for 22-26 times before booting Windows. I paid to get the ability to clean the registry (trial only diagnose, doesn't clean). After having cleaned the registry, the slider usually runs 4-8 times across the screen now. The other aspects of my day-to-day computing also sped up after this. Starting OpenOffice Word Processor took 2 minutes before this, apx 25-45 secs after.
The program I recommend to all those not willing to pay for Boostspeed is CCleaner. It's fast, efficient and easy to use. If I understood the registry better myself, I would probably use HiJackThis, but that's a bit higher up in education than where I am right now.
To summarise and answer your question: Registry cleaners work. But not all of them work good. The only regcleaners I trust, are Boostspeed, CCleaner and HiJackThis (but I don't know registry well enough to use it without a How-To)