JV16 PowerTools 2008 FTW!
The developer, Jouni Vuorio, was one of (if not the) the first to code a good registry cleaner sometime before 2003 with
RegCleaner.
It was a freeware tool but now he develops JV16 PowerTools as a shareware product.
Unlike many other registry cleaners that simply remove invalid registry values, JV16 also attempts to repair and delete if irreparable.
His product is very optimized, frequently updated and offers a ton of features not only for the registry but for files/folders as well.
Oh, and his trial version does not limit the functionality at all. You have a fully featured product for 30 days.