Greylisting relies on passively verifying the behaviour of the sending SMTP server. The first time an incoming connection is made from an unknown server, the delivery is rejected with a temporary failure error message. This temporary failure message causes a normal sending server to try again later, but it seems that a typical high-volume message sender used to send bulk mail will not bother trying again. If the message delivery is attempted a second time, the greylist filter lets the message through, concluding that the sender is legitimate. Subsequent messages from the same sender are then let through on the first try in order to avoid unnecessarily delaying mail. Messages that are sent once and never retried never make it through the filter.
I have been keeping a history of messages caught by various spam filters. The "spam" line is spamassassin, the black line is the spamcop DNS-based blacklist, and the others are custom filters for specific kinds of email worms. Since implementing greylisting, the amount of spam that enters my mail system has been reduced by about 95%.
I also have some graphs of greylisting status, which report the counts of senders in the greylisting database. The green indicates the current number of legitimate senders seen within the last 10 days. The blue line indicates the current number of senders that have only tried once within the last six hours. Multiplying this value by 4 gives approximately the number of message blocked in the last 24 hours, which matches well with the 200 to 300 spam messages previously caught by my existing filters.
I have been watching mail logs pretty carefully and have not noticed any messages that should have been accepted but weren't. Some others who have experimented with this technique have noticed some messages were blocked that shouldn't have been.
For reference, I'm using the qgreylist implementation along with qmail. This implementation differs from the original greylisting paper by only considering the sending server IP address (instead of the ip/sender/recipient triplet) when making the decision to accept or reject an incoming message. This is much simpler and appears to be sufficient to block the vast majority of bulk mail.