I'm late to this discussion but I haven't gotten any spyware crap on my system in months since I started a dedicated lock down of the machine.
I do use IM (Trillian, MSN, and AIM) and used correctly there's no more chance of getting spyware from it then a web browser. I also use emule and soulseek with no problems.
1: Firewall software
This should be the first line of defense. This keeps your ports closed so if someone scans you you won't have open ports to the Net. It will also tell you if a program is trying to use the Internet; if Silly game demo.exe is calling home, you'll know with a firewall. Even more so, if you don't know what silly game demo.exe is you can look it up online and see if it is known to be spyware. Otherwise it can connect to the internet silently.
I heard ZoneAlarm and Norton Internet Security were okay. I like BlackIce, but it's hard for newbies to configure. <y favorite is Agntium Outpost, it looks and works well and it is easy to get working. This software is the most important piece of the puzzle. With open ports worms like Blaster can easily get on your machine.
2: As was mentioned a NAT firewall is a good idea (I however, had been runnning for several months without NAT but with all the other things in place and didn't get any spyware outside of relatively benign cookies). For someone like me who runs a lot of P2P software (gotta download Japanse TV somewhere) NAT is a pain in the butt, but for normal use it can really help to lock down a network and machine, since it will keep connections outside connections from connecting to you.
3: Antivirus software. This has to be kept updated. I get Symantic Corporate from my University, but Norton, Mcaffee, F-prot, and Panda are all good. Scan anything you download, especially rar, zip, and exe files. AND KEEP IT UPDATED!
4: Don't use Internet Explorer and Outlook express. I use Firefox for web browsing and Thunderbird/Eudora for mail (if I have to, I tend to just use webmail). Firefox has many great features, including themes, tabbed browsing and hundreds of useful plugins. Other good browsers are Opera and Camino for the Mac (though Macs are far less prone to this crap).
5: Dedicated scumware checking: In a well established aquarium, you shouldn't have ammonia. But you still need to have a check for it. Ditto with spyware. I run both Spybot and Adaware regularly.
6: Disable the Windows XP services you don't need. Mac OSX does this automatically. Here is a good walkthrough of everything you need to do for it:
http://www.blackviper.com/WinXP/servicecfg.htm
Now, the reason someone is telling you not to remove files with Ad-aware is this: some worms/viruses will attack and attach themselves to windows networking files. When you remove it, you screw up windows networking and cause other problems (this happened to me w/ spybot and what prompted the lock down). Obviously the scumware people do this so you won't uninstall their crap next time. The best way to test this is to quarientine first. If you reboot and there's a problem its probably the taking out of the spyware.
This is why I believe spyware being on your machine is a failure. Taking it out can cause problems. As with aquariums, prevention is the best cure. Like I said in months of computing (including always being logged on to two or three IM services) I've never had a problem. Before this dedicated lock down I would always find some scumware hidden somewhere on my machine and it really killed my performance.