Yep. I used to work at DreamHost and our customers would run into issues with Gmail greylisting incoming mail. In fact, they do it like crazy.

In a lot of cases, adding an SPF record for the sending domain would clear things up.

It is disturbing how many DNS/domain hosting companies still have zero support for SPF.

It is A, MX, CNAME, and MAYBE a couple of other common record types. But a TXT record? No chance...

I had to move to Route53 just for this functionality.