Gmail seems to have trouble receiving email from my server. I checked and couldn't find it on any blacklists. The RDNS settings are right. Anything else?
Yes. I ran diagnostics here: http://www.mxtoolbox.com/diagnostic.aspx and everything came back green. I checked the SPF record and got these results: Code: Type Domain Name TTL Record TXT mail.mydomain.com 24 hrs v=spf1 mx ~all Record: v=spf1 mx ~all Prefix Type Value Prefix Desc Description + mx Pass Match if IP is one of the MX hosts for given domain name ~ all SoftFail Always matches. It goes at the end of your record.