Install AdAware SE, and do the updates.
I then do a "msconfig" and kill anything I don't want running.
Control Pannel / Add - remove programs and uninstall anything that shouldn't be there. Sometimes they are here, sometimes they aren't.
Boot to safe mode.
Run full scan with AdAware and remove anything it finds. May have to reboot and do this again as some of the malware hides other malware.
If this doesn't work, or something keeps coming back after you clean it out, do a google search on that particular one.
If you get the pay version of AdAware, it has AdWatch which blocks anything from being written to the registry. Start that while you do your cleanups and watch for what it says is tring to make the changes and hunt it down and kill it, one at a time.
Or format the drive and then switch over to FireFox.