I have had to clean some of that stuff out by hand - going into the Registry (ugh!) and picking out the pieces; then killing off the processes by hand (you have to dig through the list, and they're not in "Applications" when you do the Vulcan Nerve Pinch.)
Rules for Anti-Spyware:
1) If you don't know what it is, DO NOT CLICK ON IT!
2) Stop using MSIE! It's a bloody bugpack on its own, and an awful lot of that stuff will automatically trigger with MSIE. Virii as well. Firefox is preferred (since it's the old Netscape core; stripped, updated, and nearly all features "manually installed:" and Netscape is abandonware anyhow, I'm not going to say to get Netscape. I'd also suggest Opera - but I don't know enough about it to actually recommend it. Don't bother with Apple Safari tho - it's a resource hog.)
3) Have a decent Antivirus/security programme. AVG is good. ESET isn't bad (I'm running it on my ASUS netbook.) Norton was good, and the engine is still good, but the interface has gotten to need too much overhead in the last few years.
4) If you don't know what it is, DO NOT CLICK ON IT! Full stop. You can activate virii, malware, spyware, and suchlike without knowing you're doing it, or even thinking you're taking effort not to.
5) If you're running FireFox, two little add-ons that come in very handy - NoScript and AdBlockPlus. NoScript will automatically block scripts, ABP will automatically block pop-up (and most pop-under) adverts. You have to manually whitelist sites, but that's quite easy to do.
6) Keep your security updated.
7) Free security is usually worth precisely what you paid for it. Don't bother.
8) Likewise, don't bother with MacAfee. From what I've had to deal with on the stuff, it can't catch a cold without written instructions (and that's still a fifty-fifty shot!)
9) No matter just how good your AV/Security software is, your behaviour still counts for much. The condom comparison wasn't far off - the pores in a latex condom are ten microns in average diameter, while HIV is one micron across on the long dimension. What's all this about "Safe Sex?" Might as well use a coffee filter... Browsing habits and response to stimuli are going to count for rather more than software will, in preventing virus/malware/spyware/adware infections...