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.
And BTW, spammers have figured out RFC822 now, so this doesn't even prevent a lot of spam.