What is this?
When a mailserver sends email to one of the many addresses we host, our server checks if it has seen this mailserver before. If it has not, or the last successfully sent email was received a while ago, it will terminate the connection, telling this mailserver to try sending the same email again after waiting for some minutes.
A good mailserver will comply since it is not uncommon that mailservers ask for retransmission in the future. However, badly configured mailservers (and a lot of spam bots) do not recognize this command and will never come back again.
Problems
Since email is delayed from hosts that are either new or do not send email to us on a regular basis, some email can be delayed. However, since there is no such thing as a guaranteed time for delivery in smtp, this should not be a problem.
Some folks argue that greylisting is offloading the problem to the sender. This is not true at all since temporary errors can always happen and every mailserver must be prepared to queue email locally in these cases.
Misc
You can see if an email to you has been greylisted by taking a look at the header lines. Our greylisting mechanism leaves a line like this
X-Greylist: delayed NNN seconds by postgrey-1.32 at efeu; TIME NNN := number of seconds that email was delayed TIME := date and time email was released by greylisting mechanism