Yes, I would do header_checks in ISPC3 if you're comfortable with that. It's pretty simple in the end. I haven't tested my new ones I wrote yet, so won't post them. But, I'm thinking that postgrey will be the best solution.
POSTGREY is an easy implementation of Greylisting:
Greylisting is a new method of blocking significant amounts of spam at the mailserver level, but without resorting to heavyweight statistical analysis or other heuristical (and error-prone) approaches. Consequently, implementations are fairly lightweight, and may even decrease network traffic and processor load on your mailserver.
Greylisting relies on the fact that most spam sources do not behave in the same way as "normal" mail systems. Although it is currently very effective by itself, it will perform best when it is used in conjunction with other forms of spam prevention. For a detailed description of the method, see the Whitepaper.
The term Greylisting is meant to describe a general method of blocking spam based on the behavior of the sending server, rather than the content of the messages. Greylisting does not refer to any particular implementation of these methods. Consequently, there is no single Greylisting product. Instead, there are many products that incorporate some or all of the methods described here.
Postgrey is a Postfix policy server implementing greylisting. Development of Postgrey started at the ISG.EE and is now sponsored by Open Systems AG.
When a request for delivery of a mail is received by Postfix via SMTP, the triplet CLIENT_IP / SENDER / RECIPIENT is built. If it is the first time that this triplet is seen, or if the triplet was first seen, less than 5 minutes ago, then the mail gets rejected with a temporary error. Hopefully spammers or viruses will not try again later, as it is however required per RFC.
I have POSTGREY running. It's blocked a significant amount of unwanted email. It's only downside, if there is any, that it delays mail delivery by 5 minutes default.