Another downside is that some poorly written applications try to deliver mail on their own, instead of using a real mailserver.
It is somehow required that the mail user knows about the greylisting setup so that he can request the other application to send the same mail again after some minutes. One real world example are those registration links you get via mail to confirm your account. It happens very often to me that I have to re-request the mail, to get it into my mailserver.