I have converted dozens upon dozens of companies over to google apps for your domain, but I have run into a certain problem a few times and was hoping that you guys might be able to help.

In short, because all the MX records for that domain now point to google, some providers are dropping all Email that is sent in an automated manner from other servers.

To rephrase as an example, site xyz.com sells widgets, and uses google apps for your domain. When someone with an Email address @qrs.com places an order at xyz.com their web server sends an order confirmation Email. The servers at qrs.com don't see that the webserver is on the list of servers to receive Email for that domain, so they just throw the Email away. They do not bounce it, they do not put it in the users spam folder, it is just gone. customerqrs.com in the same way does not receive status and shipment notifications and not having the information they need and thinks that xyz.com scammed them and reverses the charge on their credit card and potentially worse, files a complaint with the BBB and or FTC. xyz.com now has now shipped thousands of dollars in custom made widgets and had all the money pulled from their account, potentially had their account frozen, has a huge battle with regulatory bodies, and egg on their face.

So.... How can I solve this scenario?
I have investigated the following paths and every one has had major drawbacks or has just been outright not doable :

add an MX record for the webserver – This causes way to much sporadic behavior.

Implement DomainKeys – seems to be not very well adopted, and where it is, seems like it would disable receipt of Emails from apps for your domain. (I have not verified that)

Implement SPF – seems that everyone that knows says this is going to cause way more problems than it solves. (again, I have not verified the problems this would cause)

Help!

My first question was going to be whether you had SPF records setup on your domain's DNS because that would probably cause this sort of thing to happen. But it appears that you don't. (Although, having said that, I'm sure you can configure SPF records to include other servers too, so that it's actually "allowed" for them to send mails. Unfortunately, I've never done that myself though...)

How are you sending the emails? Presumably you're using an SMTP service of some sorts. Are you sure that the server sending the mails hasn't just been blacklisted? Is it possible to send automated email via Google's SMTP servers?

It should theoretically make no difference whatsoever whether the server sending the emails is the same as the server receiving them, so I'd be double-checking that's definitely the case before going any further.

well, the one that I am using right now is using Swift Mailer to compile the messages and Sendmail to sent them....

As for blacklisting, it happens every once in a while, and we know how certain domains (like yahoo) respond to blacklist issues (give a 553 error) and that is not happening.

Our first solution was to try google's SMTP servers, and that worked so finicky that we gave up on that. Mostly, google was either not allowing us to send, or the email was bouncing because of different spammy attributes... That said, at least we were getting bounces...

You should certainly try SPF, because how else are "some providers" going to be convinced that your outgoing SMTP email is legit?

I'm not using Google Apps for your Domain, but for one of my domains I send email from my own computer (80.177.172.149), my hosting company (nfshost.com), and Gmail (aspmx.googlemail.com).

Therefore, my DNS includes the following TXT record. It won't directly transfer to your situation, but you get the idea of how it works:

v=spf1 ip4:80.177.172.149 include:nfshost.com include:aspmx.googlemail.com ~all