I use and enjoy all the utilities in Fix-It Utilities 5. The Reg cleaner seems to be very effective for me. Can usually be found for $30 or so in CompUSA or Best Buy and such.
Depending on what you are looking for when you say "regcleaner" there are a few things out there.
In the pay category, Norton's registry cleaner seems to do a good job, but I hate all the extra crap that comes with it. Last I knew, though, you didn't have to install everything. Kckazdude had a suggestion, but I don't have experience with that.
On the free end of things, you might take a look at RegScrubXP or something like CCleaner. Both do a pretty good job, both free.
Ace Utilities is the safest registry cleaner I've found - and has excellent additional system maintenance tools. Ace's one-button cleanup wizard makes routine system maintenance ridiculously easy - history+registry+junk files+shortcuts.
Ace has no registry-search function. As a registry cleaner, Ace always returns far fewer removal candidates. This program is as close to 'foolproof' as you're likely to find. 30-day trial is fully-functional.
For registry-search and for deeper inspection of the registry, I use the excellent free RegSeeker.
Search for RegCleaner 4.3 (a freeware version of the one in the jv16 power tools mentioned above). I have been using it for years and have never found anything better for cleaning out the registry.