The last time I installed Glary Utilities, my Anti-Spyware/adware/unwanted-software/other-grayware program said that it was a program that would not do what it advertises. (Eg: Wont remove as many unnecessary registry keys as it says it does)
Personally, I use two utilities:
1) A utility that is kept updated, and that is often (or used to be more than it is now) recommended on ComputerHope, CCleaner (Formally: Crap Cleaner)
www.ccleaner.comFree, no ads, but, you should de-select "Yahoo Toolbar" options. We have and FAQ article about it:
http://www.computerhope.com/forum/index.php/topic,22078.0.html2) A less common, but great tool. Has a few miscellaneous tweaks as well. RegSeeker.
RegSeeker does a very extensive search of the registry, and compares it to all the files of your system, removing more than what your usual registry program would. The con of this, of course, is that it takes a lot longer to run. Still, it can be very beneficial.
Most "Experts" will tell you that Registry cleaners are for losers, and that you should go through the registry yourself...
Though in some cases, with some more risky software, this can be true, there are a lot of registry keys you will never find, since there are hundreds of thousands of keys, and your not likely to go through all of them.
Key idea:
Always back up the registry before removing keys. CCleaner and RegSeeker both have built in back up tools.
Do I need to start my computer in safemode to run registry cleaning software?
Not necessarily. In some cases, it might be faster. There are some unneeded keys that will be "locked" when trying to remove in normal mode, and safemode will allow you to remove some of these. Still, it usually wont yield a considerably higher amount of keys deleted when compared to ones removed in Normal mode, rendering it not necessary to restart in safemode. You might still want to do this every, say, 4 months or so. Its definitely not a weekly/monthly thing.
How often should a registry scan be initiated?
Once a month, depending on how much software you have removed or installed. Some people prefer to run a registry tool right after an installation, or uninstallation, to take care of keys "left behind."