5.4.312: Microsoft 365 DNS query failed for recipient

What it means

Exchange Online tried to resolve the recipient domain’s MX or the address of its mail host and the query itself failed: a timeout, a SERVFAIL, or a refused answer. The text usually reads like the example, with an error name after it. Microsoft keeps retrying for a while and returns the NDR once the message expires.

The difference from 5.4.310 matters. There the domain clearly does not exist. Here the domain may well exist but its DNS is unreachable or broken, so the fix lies with whoever runs the recipient’s nameservers. A DNSSEC validation failure looks the same from Microsoft’s side, because a validating resolver turns it into SERVFAIL.

Likely causes

• The recipient’s authoritative nameservers are down, firewalled, or only some of them answer.
• DNSSEC is broken: a DS record at the parent no longer matches the zone’s DNSKEY after a key or provider change.
• Lame delegation: the parent lists nameservers that do not host the zone.
• The MX target is a CNAME or points at a hostname whose own lookup fails.

Checks that apply

• DNS Server Audit Tests every nameserver for the zone and flags lame or unreachable ones.
• DNSKEY Lookup Shows the zone’s DNSKEY set so you can compare it with the DS published at the parent.
• DS Lookup Shows the DS record at the parent, which must match a DNSKEY or validating resolvers fail.
• MX Lookup Confirms the MX target resolves to an address once DNS answers again.

FAQ

Does Microsoft retry a 5.4.312?

It retries while the DNS failure lasts. The NDR you hold is issued when the message finally expires.

The domain resolves for me. Why does Microsoft fail?

Your resolver may not validate DNSSEC or may have the answer cached. Check the zone with a validating resolver and test each nameserver directly.