You didn't say what software package you are use as a mail server or email gateway.
I like Symantec/Norton. They make software that scans the email gateways and another specifically designed for MS Exchange.
The trick is to set the software up to scan it as the mail enters the server and not the desktop.
This prevents relying on the users and desktop software. The user is the week link, if they don't recognize trouble and then do some thing stupid, like read an infected email, the server might beet to death from the inside out. (You probably figured that out.)
Also, besides scanning at the gateway, make you scan at the gateway deep enough. What I mean about that is:
If I set it scan the message text only it will only lookfor malicious code in the text not the attachment.
If you set it to scan text and the attachment it may only scan the first layer attachment. If it is an email that has an attachment inside an attachment inside an attachment... or a zip inside a zip...
you can still get burned.
Symantec allows you to scan 10 layers deep.
If it does kill it at the gateway, it can kill it at the PO Box.
You can also set notifications so if it does kill a virus-infected email it will send the administrator and receiver an email with the particulars about the sender. Then the email can be regenerated without the virus if necessary or so your IT guy can tell their IT guy he has a problem...
Check Out
http://enterprisesecurity.symantec.com
GoodLuck