Spybot: Search and Speak Sternly
I ran Spybot on a system last night that was badly corrupted by spyware. It found a bunch of issues which I asked it to fix. Told me it nuked the problems. Then I ran it again and it started reporting exactly the same problems. I let it finish and again requested it fix them. Told me it did.
Rebooted and ran Spybot again. Lo and behold, it found all the same problems still affecting the machine.
OK. So I then ran AdAware, which found a pile of problems and offered to fix them. I took it up on it's kind offer and to my glee it actually did what it said it'd do.
I'd never had that kind of difficulty with Spybot before, but I've recently upgraded from v1.2 to 1.3. In retrospect, perhaps not the best idea...but who knew?