I discovered that the problem was that although we had SPF records set up for our domains, we did not have a DKIM record associated with our domain. In order to add a DKIM record in Google Apps, you need to do the following:
- Go to the Admin Console
- Click on "Google Apps"
- Click on "Gmail"
- Scroll down until you see "Authenticate Email" and click that
- Select the domain you wish to add DKIM to
- When it asks what prefix you want to use, simply use the default of 'google'
You will then see a TXT record in two parts, one piece has the domain and the other has the actual TXT record. You need to go into your DNS settings on your server for your domain and add this record. If your DNS control panel does not allow you to add the domain of
google._domainkey, simply make the domain fully qualified like
After you do this, give the DNS record a little bit of time to propagate and then click "Start Authentication" in the Google Apps admin panel. If you see a green checkmark, you've done it, and email should start flowing through the SMTP server once again.