This is one of the reasons I use Google Apps for Business for email (that and I find running mail servers tedious) as deliverability is consistently simpler.
Having to use a Google product instead of your own mail server, in order to have your email delivered to Google customers, sounds like anti-competitive business practices to me. You'd think they'd be a wee bit more careful with something like that given EU interest in them...
It also isn't enough. Some of our gmail users' email (sent through the gmail smtp server with oauth) will be marked as spam in gmail. Very frustrating!
Your mail server isn't real competition to Gmail. Yahoo and Outlook probably are, but considering Gmail handles their mail fine, I'm not sure "anti-competitive" is the right angle here.
I doubt there are very many lawyers on the spam protection team. I also doubt the people on that team have any intention of harming minor-league competition. So it's not particularly surprising that they aren't more careful about avoiding something that a) is not well-known to them, and b) they don't think they are doing.
It's just as fucked-up for our use of GApps, and customer service is just as absent for paying customers as free ones.
Microsoft could own business email again just by answering the phone.
The problem with this apart from the cost is that all the other big email servers are more likely to mark your email as spam if it comes out of google apps :(
Do you actually mean Google Apps (i.e. Gmail) or are you thinking of Google App Engine? Because I don't think most other providers particularly distrust Gmail.