I've had and still have similar issue like you do. I have my own smtp server, which sends some alerts to my google apps account. I've setup my Google Apps account to white -list all email arriving from my mail server, whitelisted source domain, added spf records, etc - but my mail still being blocked. First, Google told me that's because I use IMAP and I should stop using it - only webmail, or exchange on iOS devices - fine, still blocking. Then I was told, that I can't attempt connection to the second MX server if first fails - done, still have problems. Two or three month later, they confirmed issue on their end with firewall blocking DDoS by blocking whole /24 subnet, with no fix in sight.

Remember, I am paid user and I went through rounds of bs with their support.

I feel sorry for those, who have to send email to Google Apps/Gmail as part of their business.

(I've posted this as a comment on original story, but decided to duplicate here, if someone will find this info helpful)