Hmmm, I've used CleanMyPC registry cleaner on Xp, vista, and 7 and I've always seen overall system performance go up. The only time it went terribly wrong was when I used the vista version on 64 bit 7....completely killed it.
Honestly, from my years of experience, registry cleaners DO help. For example, with Kaspersky Internet Security 2010 being a pretty major software package installed on your machine, when you uninstall it it commits jihad on the registry. Boot time goes from a solid 30 seconds to over a minute. Windows Explorer can act like vista, you open more than two windows and it freaks out. With a decent registry cleaner, it can take errors out and also defrag it. That's actually the most important there, defragmentation of the registry. Make sure the program you use has defragmentation capabilities.
And also, with use of 7 and registry cleaning and defragging, I can tell you for sure that the most you'll ever do it is probably one or two times every two weeks. Unless if you constantly install and uninstall major software that is. The NT 6.1 kernel is much more stable than 6.0. Yep.