Email Security

Restoring Microsoft 365 Mail Flow After a Domain Re-Add

Articles · July 2026 · Ioannis (John) Konstas

Removing an accepted domain from a Microsoft 365 tenant and adding it back sounds like a no-op. It is not. The re-add silently regenerates parts of the mail infrastructure that your DNS zone still describes in the past tense, and the failure modes are scattered: inbound mail may keep flowing while Outlook profiles refuse to configure, or outbound mail lands in spam while everything looks green in the admin center. This is the recovery procedure I use — it takes a zone from "email is acting weird" back to fully authenticated mail flow, and it applies equally when you inherit a tenant someone else broke.

What a re-add actually destroys

When a domain leaves a tenant, Exchange Online tears down tenant-side state that does not come back identically:

The MX endpoint name can change. Inbound mail for each domain terminates at a tenant-scoped hostname under mail.protection.outlook.com. On a re-add, the regenerated endpoint often carries a numeric or letter suffix (example-com0e instead of example-com) because the original name is still reserved by the deleted registration. Your old MX record now points at a name that may resolve — but is no longer yours.
DKIM signing configs are deleted. DKIM — DomainKeys Identified Mail, the mechanism that cryptographically signs every outbound message so receivers can verify it originated from your domain and was not altered in transit — is provisioned per domain, per tenant. The private keys are gone. The selector CNAMEs in your zone point at key records that no longer exist, and signing is off even if the toggle was on before.
Client discovery must be re-proven. Autodiscover behavior for the domain resets along with the domain registration, so any DNS problem that was latent before the re-add becomes fatal now — clients re-run discovery from scratch instead of using cached profiles.

What survives: your SPF TXT record, your DMARC policy, and any third-party records. That asymmetry — half the records right, half stale — is exactly why the symptoms look inconsistent.

Triage in the right order

Work outside-in with dig before touching any portal. Five queries tell you the whole story:

# 1. Where does inbound mail go?
dig +short MX example.com

# 2. Does client discovery reach the provider?
dig +short CNAME autodiscover.example.com
dig +short autodiscover.example.com        # A-record fallback — see below

# 3. Who may send as this domain?
dig +short TXT example.com | grep spf

# 4. Are signing keys published?
dig +short CNAME selector1._domainkey.example.com
dig +short CNAME selector2._domainkey.example.com

# 5. What do receivers do with failures?
dig +short TXT _dmarc.example.com

The MX answer should be your tenant endpoint — suffix included — exactly as the admin center's DNS page states it today, not as you remember it. Verify against the portal, never from memory: the suffix variant is the single most common stale record after a re-add.

The proxied-record trap

Here is the failure that wastes the most hours, because every record looks correct in your DNS provider's dashboard. If your zone sits behind a CDN or reverse-proxy layer (Cloudflare and similar), each record has a proxy toggle. A proxied autodiscover CNAME still displays as pointing to autodiscover.outlook.com — but publicly it resolves to the proxy's edge addresses, and every client request terminates at the CDN instead of the mail provider.

The diagnostic signature is unmistakable once you know to look for it:

# BROKEN — proxy is answering:
$ dig +short autodiscover.example.com
104.21.x.x        # CDN edge address
172.67.x.x        # CDN edge address

# HEALTHY — CNAME chain reaches the provider:
$ dig +short autodiscover.example.com
autodiscover.outlook.com.
autodiscover.outlook.cloud.microsoft.
52.96.x.x

Why it breaks: Outlook's discovery client is not a browser. If the proxy layer runs bot mitigation or a challenge mode — common on zones under active attack protection — the client receives a JavaScript challenge page instead of the discovery XML, and it can never solve it. Profile creation fails with generic "cannot connect" errors while the website on the same zone works perfectly, which sends you hunting in all the wrong places.

The rule is absolute: every mail-plumbing record — autodiscover, the _domainkey selectors, SRV records for SIP/federation, and anything an MX resolves through — is DNS-only. Proxying is for humans with browsers; mail protocols must bypass the edge entirely.

The fix is one API call or one toggle: switch the record to DNS-only (grey cloud). No content change is needed when the target was right all along.

SPF: one record, every sender

SPF survives the re-add, but audit it anyway — it is the record most likely to have drifted if the domain also sends through a legacy webmail platform, a marketing tool, or a hosting provider's relay. Every active sending path needs an include, and Exchange Online's is non-negotiable:

v=spf1 include:spf.protection.outlook.com include:relay.example-host.net -all

Missing the provider include while MX points at that provider is a silent half-failure: inbound works, receivers accept your outbound on reputation for a while, and then a strict verifier starts quarantining you. Keep it to a single TXT record — multiple SPF records at the same name is a permanent error (permerror) — and stay under the 10-DNS-lookup limit that nested includes burn through.

DKIM (DomainKeys Identified Mail): rebuild, don't repair

Because the re-add destroyed the signing keys, the old selector CNAMEs are dead weight. Rebuild from the provider side first:

In the security portal's DKIM page, select the domain and create new keys. The portal returns two CNAME targets — one per selector, so keys can rotate without further DNS edits.
Publish both records exactly as issued, DNS-only. Current Exchange Online targets land under a namespace of the form selector1-example-com0e._domainkey.<tenant>.p-v1.dkim.mail.microsoft — note that the MX suffix reappears here, and that newer tenants get p-v1/r-v1 zone variants. Copy, don't transcribe.

Verify propagation from the outside before touching the enable toggle:

for r in 1.1.1.1 8.8.8.8 9.9.9.9; do
  dig +short CNAME selector1._domainkey.example.com @$r
  dig +short CNAME selector2._domainkey.example.com @$r
done

Enable signing. Expect the provider to publish the public-key TXT at the target only after enablement — an empty TXT behind a correct CNAME is normal until the toggle is on.

The negative-cache gotcha

You publish the selector CNAMEs, all four public resolvers confirm them, you flip the enable toggle — and the portal insists "CNAME record does not exist." Nothing is wrong. The provider's resolver queried the name before you published it, received NXDOMAIN, and is entitled to cache that negative answer for the duration of your zone's SOA minimum TTL:

$ dig +noall +authority SOA nonexistent-probe.example.com
example.com.  1800  IN  SOA  ns1.example-dns.com. hostmaster.example.com. ...
                ^^^^
                negative answers cached up to 30 minutes

Query your authoritative servers directly (dig @ns1.example-dns.com) to prove the records are live, then simply wait out the SOA minimum and retry. Portals phrase this as "up to 4 days" to cover pathological TTLs; with a competently configured zone it is bounded at your SOA minimum — typically 30 minutes. Knowing the exact bound turns a vague "come back later" into a scheduled retry.

Prove it end-to-end

Dashboards lie by omission; message headers do not. Send from the recovered domain to an external mailbox you control and read the authentication results:

Authentication-Results: mx.example-receiver.com;
       spf=pass  smtp.mailfrom=example.com;
       dkim=pass header.d=example.com header.s=selector1;
       dmarc=pass action=none header.from=example.com

All three must pass, and header.d must be your domain — not the tenant's onmicrosoft.com fallback, which is what you get when DKIM enablement didn't take. Then confirm the client path: a fresh mail profile on a device outside your own network must configure without manual server entries. Testing discovery from inside your infrastructure can mislead you — egress filtering and VPN routing produce local-only failures that have nothing to do with your zone.

Finish with DMARC enforcement

A re-add is the right moment to advance DMARC, because you have just re-verified every mechanism it depends on. If you sat at p=none before, collect a week of aggregate reports to confirm no legitimate sender is missing from SPF/DKIM, then move to p=quarantine, then p=reject:

v=DMARC1; p=quarantine; rua=mailto:dmarc-reports@example.com; fo=1; adkim=s; aspf=s

With enforcement on, the authentication stack you just rebuilt stops being paperwork and starts actively discarding forgeries of your domain.

The recovery checklist

MX — matches the admin center's current endpoint, suffix and all; verified with dig, not memory.
Autodiscover — CNAME to autodiscover.outlook.com, DNS-only, publicly resolving to the provider's chain, never to CDN edge IPs.
Every mail record unproxied — selectors, SRV, anything mail-protocol clients touch.
SPF — single TXT, one include per active sending platform, -all, under 10 lookups.
DKIM — keys regenerated post-re-add, both selector CNAMEs published verbatim, signing enabled, header.d confirmed in real headers.
Negative caching — SOA minimum known; portal "record does not exist" errors retried after that window, not debugged.
End-to-end proof — external inbound delivery, external profile setup, and a three-pass Authentication-Results header.
DMARC — advanced toward enforcement now that the foundations are re-proven.

A domain re-add is a partial rebuild wearing the mask of a no-op. Treat it as one: enumerate what the tenant regenerated, republish what changed, keep every mail record out of the proxy path, and let message headers — not dashboards — declare the incident closed.

← All articles

Research and direction by Ioannis (John) Konstas; compiled and finalized with AI assistance.