email bounces – Exchange 2010 rejecting some Gmails

My work Exchange server just recently started rejecting some emails sent from Gmail accounts. Some emails sent from Gmail accounts come through just fine.

We have our spam protection through Google so our MX record points to Google where the email is scrubbed for spam and the good emails are forwarded through to our Exchange server. Recently some emails sent from Gmail have begun to bounce. I can check the logs on Google and see that the emails were successfully received and passed through to our Exchange sever. Our server is rejecting them and there is no sign of these emails in the Exchange log files.

I worked with Google who said everything was correctly configured. My personal email is a custom domain where my MX record is pointed at Google. Google hosts my email but it’s my domain and I have full control over DNS. Emails from my personal domain were being rejected by my work Exchange server (never had before). At Google’s suggestion, I configured SPF, DKIM and DMARC (for my personal domain) – none of which were configured before. When I did, suddenly my emails flowed through.

Why would my work Exchange server suddenly care about SFP and DKIM? I don’t believe Exchange 2010 even has built in support for those checks and I haven’t added any addons to my server. The bounce emails aren’t very informative, just saying “The recipient server did not accept our requests to connect.”

I have recently installed three Microsoft updates on the work Exchange server (2008 R2) but they are all Security and Quality rollups and shouldn’t affect the Exchange server specifically. Any ideas what may have happened or what I can do to troubleshoot?