Cannot receive emails from Microsoft 365 tenants anymore because of DNS propagation issues

[hallo8]

Problem Description

We use Microsoft 365 for emails. A few weeks ago, receiving emails from other Microsoft 365 tenants stopped. We can receive emails from other mail providers (e.g. gmail, self-hosted mail servers). We tried sending mails from many different M365 tenants. Not a single one was delivered successfully.

We use multiple subdomains (e.g. linz.coderdojo.net, wien.coderdojo.net). The problem happens only with one (linz.coderdojo.net) although the DNS setup is identical for all of them.

The domain in question (linz.coderdojo.net) worked in the past. The problem appeared suddenly without any config changes on our side.

Problem Analysis

I have been working on the issue with Microsoft support for weeks. After thorough investigation, Microsoft finally told me that it seems to be an issue with DNS propagation of the MX record of linz.coderDojo.net. One can see e.g. with https://www.whatsmydns.net/#MX/linz.coderdojo.net that the MX record is not propagated to some regions in the US. We compared the propagation with domains that work (e.g. wien.coderdojo.net). The DNS propagation problem does not appear there.

Question

We are pretty much out of ideas by now. Any ideas if Microsoft’s analysis is correct? Any idea what we can do/change to fix the propagation issue?

[epic.network]

You have a CNAME at linz.coderdojo.net. No other RR types are permitted at the same label as a CNAME (DNSSEC excepted). Its existence invalidates both the TXT and MX records that you have published at that and name. See section 2.4 in RFC 1912 for more information.

[hallo8]

Thank you for pointing that out. I wasn’t aware of that and I am going to fix it. Do you think that this might be the reason for the problem though? https://www.whatsmydns.net/#MX/linz.coderdojo.net shows that MX record is delivered correctly everywhere in the world, except in one region in the US.

[epic.network]

The MX and TXT records published erroneously, but Cloudflare allows it regardless. An RFC compliant resolver should ignore them.

[hallo8]

Thank you so much for your tip! After removing CNAME (I switched to A record), DNS was propagated correctly and I received an email from M365 successfully .

[epic.network]

When a CNAME is set to Proxied it is published as A and AAAA records. I don’t know if that record is something that you would want to proxy, and clearly it is already working as desired as an A record. I only mention the proxied CNAME behavior as it is not intuitively obvious.