Stopping open proxies and open relays

I am looking for ideas to stop the spam created by compromised Windows PC's. This is not about the various worms and viruses replicating but these boxes acting as open relays or open proxies. There are valid reasons not to run antivirus software, coupled with clueless users, this results in machines that SPAM again just a few hours after having been cleaned. Adi