Are there legitimate registry cleaners?

Yes lots.

Well...
Are any worth whatever it is they are charging, and if so, what are they?
(I like guinness - just a small verbal bribe for a complete answer this time)

There is NO need to pay for this type of program when there is the excellent CCleaner. (http://www.ccleaner.com)

I use CCleaner too. Great suggestion, it not only cleans the registry, it is full of other helpful system cleanup functions.

Highly recommended.