Take a look at this.
It's called greylisting, it's very effective.
Before sending any email to any mail server, use a daemon to filter messages using greylisting. It is designed to hurt spammers, if they are not RFC compliant (most spam programs aren't), they won't be able to be whitelisted and their email will be discarded.
Spamd is a daemon available on OpenBSD, they made it handle greylisting, as well as whitelisting (to mitigate delays introduced by greylisting trustworthy SMTP servers). Initially it could be used to tarpit spammers, sending them 1 byte per second, to make them waste time and make the world a better place.
Spammers will adapt, so they added greytrapping. It's basically detecting bad RCPT-TO fields and blacklisting hosts who offend the rules, they will be un-blacklisted later on automatically.
Spamd also tarpits all greylisted hosts for 10 seconds, cutting down another slice of spam mail. It allows you to create a script and choose if you want to blacklist some greylisted hosts based on whatever you want (a blacklist found on the web, A/MX records for the SMTP server, etc).
It doesn't require much resources, you can put it as a front end to your mail server clusters or run it on your gateway (if you're running OpenBSD that it, else you'll have to look for another solution).