First, do a clean install of the OS and all allowable software. Lock it down so everything works together. Now, make all the users just plain users. In XP, they shouldn't be able to load any software themselves. This means that automatic installations that spyware depends on will be shut out (at least the vast majority of them), and the spyware just can't get in.
Now, you WILL catch bloody hell from your users. But these are not THEIR computers-they belong to the company. So there's no reason for them to install ANYTHING that the company didn't already install. If they whine, it's just tough. Not having to rebuild their computers every few weeks will actually improve their (potential) productivity.
What? I have a low appreciation for most computer users? ME?!? You betcha! Too many examples of Saturday morning cartoon adicts who think they can do brain surgery because they saw it in a movie once... But I digress.
Oh, and set up the antivirus software so that it a)updates from a server on your local network, b)automatically updates DAILY, and c)does not allow the user to turn it off, change its settings or otherwise bork with it. Have your server check for virus updates HOURLY (I'm not kidding). I've been in situations where the above (both the configurations and AV setups) have kept thousands of users up and running during serious attacks. It's a pain to set up-but you only have to do that once.