Just for the record, I've had tremendous success on 2000/XP systems using a tool called ERUNT which makes date-stamped copies of the registry on demand and at startup. This doesn't have all the overhead & other issues of System Restore but makes it trivial to revert to an uninfected registry, then clean up the mess. I also use a BartPE CD to boot infected systems and look for files with appropriate modification/creation dates (and nonsense names, and Program Files directories, etc). This, of course, does not prevent problems with VERY sneaky malware that, for instance, patches "beep.sys" to load, but will give you many more ways to attack these problems.
Of course, ERUNT must be installed and in use *before* the problem occurs!
And, thanks to UAC, ERUNT doesn't properly make backups at Vista startup so is much less useful than on XP/2000 systems.
One final note: I install the Recovery Console on every XP/2000 system that I touch. ERUNT creates its backups in C:\WINDOWS\ERDNT which is accessible under Recovery Console, so it's easy to put a clean registry in place.