Or more specifically – Never put a CNAME record on your Root Domain if you have other DNS records set-up (or might add them in the future).

I found this out the hard way when I was trying to receive a validation email from an SSL certificate supplier. The email never arrived, however I was sure my email was working as I was receiving other emails just fine (although this is not my primary account and I hardly ever use it). I realised something was definitely wrong when I tried to send myself some test emails from my work account and they never arrived either.

To cut a long story short, the problem was caused by having a CNAME entry against the root domain. It turns that this is intended behaviour according to rfc1034 (DOMAIN NAMES – CONCEPTS AND FACILITIES) page 15, which reads;

If a CNAME RR is present at a node, no other data should be present; this ensures that the data for a canonical name and its aliases cannot be different. This rule also insures that a cached CNAME can be used without checking with an authoritative server for other RR types.

The moral of the story is that, just because something seems like it’s working, does not mean it’s working correctly, especially when it comes to DNS and mail servers.
As a footnote. If I search Google for “CNAME on Root Domain MX” in hindsight, the returned results would have saved me allot of time and head-scratching. While searching using terms which matched the actual symptoms observed such as “mail sometimes being send to A-record” or “MX record sometimes being ignored” returned less helpful results. I find it interesting that knowing exactly how to search and which search terms to use can be massively important when trying to investigate a problem like this.