I work for Gateway tech support; I've seen what spyware can do to a PC, and the level of frustration it produces in their owners...and it ain't pretty. You'll read the following and say I'm paranoid, but my PCs run smooth, clean and virus/spyware free.
Gateway sells SpySweeper, and indeed it seems to be very good. (I was initially doubtful, but when I installed it at home and SpySweeper found more crap than Ad Aware and half the other sketchy "anti-spyware tools" out there, I was convinced.)
I also use SpyBot S&D. I run SpySweeper & SpyBot once a week, back-to-back (after ensuring that they've been fully updated). Then I turn off my PC, reboot and run 'em again. (Some spyware can be flushed out with a reboot.)
Once a month I'll even fire up Ad Aware just to see if it can find something that the other two can't.
This is on top of Norton Internet Security 2005 (which isn't too shab), Mozilla Firefox and a router w/ hardware firewall.
There's no playing around with spyware--it's highly pervasive, exceptionally sophisticated and damn stubborn to remove, and I have no intention of reformatting my hard drive because of it..!