I've talked about greylisting many times in the past when detailing some of my anti-spam measures. For those that don't know what greylisting is, the elevator pitch is that it produces a temporary SMTP error to incoming mail relays, refusing the mail on the first attempt. If the relay attempts to send the same message again (as identified by the sender/recipient/relay tuple), it is accepted, and that tuple is then not blocked again for some long period of time. The upshot of this is that most spammers blast mail out without worrying about queueing failed requests. They get what they get, and the overhead of dealing with SMTP errors isn't worth the effort. For deeper reading, take a look at Evan Harris' greylisting information.
For a number of years now, I've been using a Frankenstein version of Evan's Sendmail::Milter-based relaydelay code. Since 2004, I've run that code with minimal modifications on mail relays of every shape and size. Matt Prigge and I even wrote a whole management Web UI that supported searching, whitelisting, and blacklisting. For my own massive spam problem, I took the 0.04 release and proceeded to rewrite it substantially, adding firewall integration that will cause pf to drop all packets from abusive hosts, and a significant number of other features that I found necessary over the years. That particular greylisting implementation is still running full-steam and is basically the only reason that e-mail is still viable for that domain, which is a three-letter domain plagued by dictionary spammers and sees a 99.99 percent spam volume.
However, both relaydelay and the code it depends on are growing long in the tooth. Sendmail::Milter hasn't been updated since 2001, and refuses to compile properly on 64-bit hosts. Relaydelay itself is showing its age and could use some new features. Thus, when I was rebuilding a mail relay recently, I decided to go with milter-greylist instead of relaydelay.
Milter-greylist produces the same results as relaydelay, but uses a completely different method. It's completely written in C and functions as a sendmail milter like relaydelay. Instead of using a MySQL database to store all the tuples, milter-greylist keeps all that info in RAM, which makes for far faster lookups but can take some tweaking on large volume servers. To retain the tuple database across service restarts and reboots, milter-greylist writes out the internal database to a flat file periodically.