Free Registry Cleaner (update)
A while back I discovered a very useful free registry cleaner. This program was fairly easy to use and never seemed to remove registry entries that it shouldn't. A recent blog post from Email Battles describes a more thorough registry cleaner that I've just tried out. Unlike Crap Cleaner, RegSeeker finds, as it did in my case, hundreds of extra bits of garbage.
Combine the two cleaners above with a registry compacting tool such as WinASO RegDefrag, and you've got a complete suite of registry maintenance tools. The longer you have been running your current version of Windows the more likely you'll see a benefit from using these tools.
WARNING: RegSeeker is much more aggressive than Crap Cleaner. This makes it more effective, but it also increases the chance that something needed will be deleted from the registry. Be sure to backup your registry file before making changes.
[UPDATE] I've been running RegSeeker for a month and a half now. On two occasions it corrupted the installations of two different programs. Fortunately I was able to re-install these programs, but please heed my warning above before running this registry cleaner.