Spyware is an increasing problem. One that isn't going away anytime soon. At any given time, I have friends, relatives complaining about spyware, popups and hijacks.

I keep a dedicated thumbdrive (it can be automatically picked up by anything>Win98). This is my tool to fight spyware, etc. Important things I have loaded on it: Ad-Aware SE, SpyBot, CWShredder, McAfee 8.0i trial (or any AV of your choice), and the latest DAT.

First I copy all contents of the thumbdrive to C:. (2) Disabled the network connection.
(3) Remove any previous version of AV and install your new and improved AV. Load the latest Definitions (DATs).
(4) Boot to safe mode. (5) Install all the good stuff (ad-aware, etc). Run them and remove bad stuff. (6) Run a full AV scan.

Last but not least after reboot, install all critical updates and SPs. (I usually keep IE 6SP1 and XP SP2 on CD just in case) (I know that the patches don't have much to do with adware, but they are the single most important thing you can do.)

It takes a little work but in the end you will remove all malicious infection. (and stop the people from calling you back, at least for a couple months