The threats facing a Linux e-mail administrator with Windows users aren't any different than those facing someone...
using Exchange, but the service opportunities are.
One important difference is the absence of per-client license fees. Combined with a reasonable expectation that what you don't mess with will continue to work, this makes it possible to pass all e-mail, in either direction, across the minimal number of servers geographically necessary to serve your users. If, for example, you had major offices in Atlanta, Sacramento and Toledo, you'd have only three Internet-connected mail servers, even if each location had thousands of users -- either connecting directly or sharing other machines operating in a store-and-forward mode, either locally or across the Internet.
What this enables you to do is copy absolutely everything, just as it arrives, to a permanent record before doing any filtering at all. That gives you the best of all best of all legal defenses: perfect records against e-mail related accusations, while giving senior management the supporting information they need to react promptly and correctly to real problems.
First, use a write-once device, buy labelled media, number them on receipt, and establish a daily or weekly procedure under which someone else replaces the media in the drive and takes storage responsibility.
Once that's in place, filter all mail -- in both directions as well as the internal stuff -- through both a spam classifier/remover like SpamAssassin and a virus scanner like ClamAV. That protects users, improves transperancy and reduces license fees for Windows store and forward servers internal to your network while letting you quickly detect and stop problems like those created by malware brought in on laptops, PDAs, or removable media.
Volumes are not an issue. At winface.com I get an average of 676 spams per day amounting, in the gzip form, to a bit under 2 megs -- about one CD a year. Even a thousand-user head office isn't going to fill a DVD a day.
Be aware, by the way, that I mention SpamAssassin and CLamAV only because I'm familiar with them. We're talking Unix here, and its not a one-size-fits-all world. Search SourceForge for mail related filters for Linux, BSD, or Solaris and you'll find lots of great stuff. Some of it may well meet your needs better than the ones I happen to know off the cuff.
Paul Murphy wrote and published The Unix Guide to Defenestration. Murphy is a 20-year veteran of the IT consulting industry.