Greylisting is the idea to reject incoming messages with an SMTP error code that indicates failure, unless the source of the message has sent e-mail to the given recipient before (or some other heuristic for "we've seen that source before"). The observation underlying this scheme is that e-mail has traditionally been a store-and-forward medium able to deal extremely well with all kinds of temporary glitches. Ordinary mail servers will just queue up a message when they get "greylisted", and try again after a while (and again), at which point the message will be accepted. The SMTP implementations used by spammers, however, seem to commonly just fail when they encounter any kind of SMTP error.
The statistics show that greylisting (I'm using postgrey) has been removing a significant part of my incoming spam burden; the green curve represents the spam and other junk detected on my personal mail server, the blue curve represents the messages that get through (still including a significant amount of spam, most of which is caught by a bogofilter installation on my laptop).
Of course, greylisting has one significant weakness: It will only work as long as it makes an insignificant dent into spammers' output (as opposed to just some sites' input). As soon as the technique becomes widespread enough to become noticeable for spammers' returns, we'll start to see SMTP implementations for spammers that implement some kind of retry mechanism. Until that happens, however, greylisting is a truly useful tool.
