Three weeks ago I’ve set up greylisting on our little qmail toaster. The technique works amazingly well on our setup:
The server used to get hit by round about 1600 mails each day. Roughly 70% of those were spam mails. Now, with greylisting activated, this amount has been reduced to just a dozen spam mails and around 350 – 400 legit emails:

The server load is also reduced because SpamAssassin and ClamAV are less busy filtering mails:

So, speaking for us, this experiment has been very successful. Exactly no real mails got lost, tons of spam was blocked at the SMTP level. Excellent. Now, let’s see how long the effects of this technique will last…

See http://projects.puremagic.com/greylisting/ to learn more about greylisting.