Even with anti-spam there still can happen some false-negative (a spam not detected), so there is no easy way for you to say what is and what is not a spam. (If it was easy all spam problem could be solved easyly).
Some choices I could give you:
1.Buy an anti-spam and tell your clients to use your anti-spam as relay, then close direct connection from clients to internet on port TCP/25.(Ironport, now is cisco and the best antispam I ever see)
2.Usually spam from inside are sent by some computer with virus or something.. not an user opening his email and sending emails (unless it's a marketing email being considered spam by RBLs).
So you could bring up a SMTP relay, a simple one not an antispam, but listening on an righ port, not 25, and tell your clients to use it as relay. the zumbi machines will try 25 and fail as you are blocking it