Just in case anybody ever finds it useful:
If you suspect (or know) that you've got some malware on your machine, and especially if your various programs don't seem able to solve the problem, you should try running your sweeps and scans in Window's "Safe Mode". It keeps the malware from hiding itself on startup and/or disabling your security software.
In XP, for example, you access the Safe Mode by pressing F8 as Windows loads. Instructions for other Windows OSs can be seen here.