Recently, we had received reports from several external parties that they were unable to send email to conetrix.com addresses. The NDR message reported "MX record not found for conetrix.com".
Simple solution, right? Not our problem. I checked several external and global DNS caches including OpenDNS, CloudFlare, and Google, and all successfully resolved records without issue. One aspect that all parties had in common was they were sending email via Gmail, specifically Google Apps accounts. I've got a Google Apps account on a personal domain, so I sent a test email that was delivered without any issues. At this point, we figured it was a transient issue and moved on.
Except it wasn't. Over a period of time, it became apparent that this issue was still occurring with fair regularity and that there was something still going on. So what if this actually is our problem? What could any possible solution be?
I had taken vacation during the troubleshooting period and came back to the office following my PTO with a mini-epiphany. We host our own DNS records. Could it be possible that these Google Apps customers couldn't connect to our nameservers to resolve the MX records correctly?
On a whim, we updated the geoblocking rules on our external firewall cluster to allow inbound DNS requests from any country (not any traffic, only DNS requests). After reaching out to the external parties to send us new email, those messages were successfully delivered and we have not seemed to have had any issues since then.
I don't know why unencrypted Google Apps DNS requests were routed through foreign countries – especially countries that were added to our geoblocking list as housing potentially malicious traffic – but it seems pretty likely that this was the case.