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.
Oh, you'll get those in an hour or so, when their mailer retires. I have never had a problem.
I did kill greylisting, though, because it breaks when the mail server that first tried to send the message is not the one that tries to send it again. Gmail does this, for example, and unless you keep up to date on Google's internal architecture, you are going to lose mail from Gmail users. Combined with being tired of waiting an hour or more for every email, this killed greylisting for me. Now I let the spammers deal with spamassassin, which is quite nice if you bump up the scores on the content and URI blacklists.
I still had the same problems others have mentioned though, where crappy registration systems were sending their confirmation mails directly from their PHP application, rather than relaying it through a smart MTA that actually understood the SMTP protocol and would do the retry.
Ultimately, too many users complained about mail delays and missing email. This is one of those scenarios where the cost of not delivering an important email may outweigh the benefits of blocking a few more invalid ones.
The issue there being that if Google ever changes their internal network structure, you lose mail until someone notices. Personally, I don't like coupling myself to other networks that tightly, and I also don't like losing email.
The Gmail issue you highlight I believe would only happen when the original outbound smtp server goes dark before it reattempts delivery. I say this because I have been receiving emails from Gmail with greylisting on for a week now.
Oh, you'll get those in an hour or so, when their mailer retires. I have never had a problem.
I did kill greylisting, though, because it breaks when the mail server that first tried to send the message is not the one that tries to send it again. Gmail does this, for example, and unless you keep up to date on Google's internal architecture, you are going to lose mail from Gmail users. Combined with being tired of waiting an hour or more for every email, this killed greylisting for me. Now I let the spammers deal with spamassassin, which is quite nice if you bump up the scores on the content and URI blacklists.