Here’s a few tips:
1. Install AdAware and Spybot, and make sure both are updated. Also copy LSPFix and HijackThis, as well as any specialized tools that you might find (ie, rootkit utility). Then restart your computer into SAFE MODE and run the stuff in safe mode (no networking). That’ll be a start.
2. On the other hand, just back up your stuff and reformat+reload. That’s what 90% of the IT pros would do. At some point, you’re fighting a program that you’ll never find, that isn’t a virus on its own, but keeps “inviting its buddies” which are viruses. Cut your losses.
Good advice. Even if you remove the most obvious problems, how do you really know something isn't still there? Just backup, and reinstall the machine to remove any doubt.