I have a client who had 30,000 entries in the registry from malware. Cutting it in half would yield 15,000. A great improvement.
I have Spybot with Teatimer. Teatimer is supposed to alert me to any changes to the registry and allow me to nix the change. Seems to work. Teatimer, that is. Spybot works for a time and then won't load. I have to re-download the whole thing to get it back.