Yikes.
Okay, some of this is redundant, but here's the best I could recommend.
Limit user access on their systems to user accounts. Use the lowest privileges possible. This helps limit installation of applications.
Use only software that you have approved in the IT department. No cute kitten screensavers, no stuff from home, no cool games, nothing that isn't known to you. Install auditing software that can check on installed software of your client systems.
Block incoming attachments that are over a particular size. Saves disk space, saves bandwidth, saves your mailboxes from getting corrupted.
Block incoming attachments that are executable. That's a big one. .exe, .com, .bat, etc.
See if you can filter mail with proper anti-spam checks. SPF checking. You can configure black hole lists if necessary. An antivirus on the mail server that is kept up to date. I don't know what mail server you're using so I can't help there, but on Linux/UNIX systems ClamAV is excellent on the server because it's a plugin that works with a range of MTA's and it catches not only viruses/malware but phishing attempts and is updates as if their team has OCD.
Install antivirus software on the clients, keep it up to date, sounds like you do that already. Make sure they stay up to date, though. We have software that sometimes just "stops" updating.
Are you centralizing storage? Keep the AV up to date on that, have it notify you of infections. Lets you stay no top of potential issues from the file server. The more you centralize your information, the easier it is for you to manage it (and back it up); your users are your users because they expect you to handle technology details. They don't want to have to care about viruses and the like so expecting them to do much involving "technical stuff" will lead to more infections and problems.
One thing we have in our setup because we have a large percentage of systems that keep their configuration pretty static (and we use user profiles on a network server) is a product called Deep Freeze; you configure the system to a state you want it in and then "freeze" it, and any changes made to the system are wiped at reboot. Delete the Windows directory, reboot, restored like nothing happened. Very cathartic to do that sometimes. BUT it means having to schedule updates (due to needing to thaw it) and we don't run antivirus on it due to update issues (plus you don't want it to update every time it reboots and says "I'm out of date!" Yes, systems can get infected, but a reboot will clear it up. We once purged an infection by essentially rebooting our building. Worked surprisingly well for a Star Trek plotline.
Do you keep up to date backups of your servers for recovering from malware?
Do you block outgoing ports on the firewall that your users shouldn't need? Especially your mail server port; only your mail server should be allowed outgoing port 25. Some malware will send messages on port 25 from workstations and will get you on black hole lists.
Set up your mail server for additional spam stop methods like tarpitting, and verify through external checkers that it doesn't relay mail.
Install malware checkers. Don't double up on antivirus. AV's tend to not play well with each other. By malware checkers, I mean something like MalwareBytes and Spybot Search and Destroy. Run them periodically. Update them frequently.
Keep all your software up to date. Adobe software, Java, Windows updates...consider installing a WSUS server locally if the number of clients warrants it.
Create images of your systems if they're standard. Makes recovery a bit easier if you can just roll out a clean image of the system. Standardize your hardware as much as possible.
Monitor your network traffic. Use SNMP on your border routers, check for unusual activity, get acquainted with "normal" network usage patterns. If something odd shows up you can investigate proactively. If you're playing with VM's it isn't too hard to set up a honeypot system that can check for unusual activity and email you if there's trouble; look up Intrusion Detection Systems for info.
Depending on the environment you could use policies to enforce whitelisting executables so only particular exe files can run on client machines, but this can quickly garner backlash from users. Use that one with care.
There are plenty of documents out there on anti-spamifying your mail servers, some of it implementation specific so you'd have to google for your particular MTA. There are also testers for remotely testing your configuration. Use them. There are appliances for spam filtering like Abaca and such as well, to help cut down on your learning curve...again, depends on your situation as to how you want to do it. At one time we had a proxy mail system in place so the first system got the email, processed it for spam scoring/blocked executable attachments/etc. then forwarded it to our mail server, so you can link incoming mail to multiple scanning methods. Document everything you do though or you can have a spaghetti blob of dependencies on the charts when you're trying to troubleshoot an issue.
And while they often ignore it, continue with the end-user education. Make or get posters. Email reminders (not boilerplate or they'll ignore them. It's like stop signs. You see them all the time, they end up blending in, honest officer I don't know what you're talking about...same thing with IT notifications. You need to tailor them and alter them so you trick the user into learning something from your notes) about new viruses and malware.
Oh, and work on your policies in the company. Ban personal storage if necessary, and personal devices, or approve them in the department. Outline what is acceptable use. Malware can and does travel on USB drives and disks.
(EDIT)
You could look at putting in a proxy server for web browser traffic as well. Depending on how elaborate you want to get, you could go as simple as Squid + plugins or purchase an appliance to handle the traffic for you. Appliances are of course more turn-key and have pretty manager interfaces, reports, etc. while Squid is free and slams you with a learning curve. But there are proxies out there with neat features like blocking particular file types and of course blocking access to sites, or at least you can use it to audit access to sites. Sometimes blocking isn't a means of censoring as much as it is a way to protect your users from themselves. If you find a way to properly configure it or an appliance with the right features you could block all sorts of bad traffic, and you can track how your company resources are being used.
Make sure all of this is in your policies as well. You have a right to monitor how company assets are being used, but your users have a right to know how you're monitoring them. And you want to be careful with the whole "how far to go before I'm too draconian thing." Your company's ethical borders are up to your company.
Also be aware that when searching for web proxy stuff there may be issues with https traffic. We had issues with that in our Squid filtering; there wasn't a simple way to block websites that were encrypted, because that's kind of the point of it. There are ways to do it, though. Appliances may be better suited to the task.
I believe you can also get some measure of protection through using OpenDNS servers as your DNS upstream provider. I haven't done this, so you might have to look into it, but I think they provide some services for things like blocking lookups to malware domains and such. If they do offer that service it may be trivial to add to your setup with a good measure of protection as a benefit.
