550 5.1.1 RESOLVER.ADR.ExRecipNotFound and IMCEAEX NDRs: fixing them with X500 addresses

Users pick a colleague from Outlook's auto-complete list, reply to an old thread or update an existing meeting, and get an NDR addressed to a long IMCEAEX-… string with RESOLVER.ADR.ExRecipNotFound. Typing the full SMTP address works. The cause is a stale LegacyExchangeDN, and the clean fix is an X500 proxy address. Here's how to decode the NDR, add the address and stop it from coming back.

Symptoms#

The NDR's diagnostic section looks like this:

Generating server: EX01.contoso.com
IMCEAEX-_O=CONTOSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=4F1C0F0B7C2E4D6F9A8B1C2D3E4F5A6B-JSMITH@contoso.com
Remote Server returned '550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found'

When Exchange Online generates the NDR (common in hybrid), the wording is longer:

550 5.1.11 RESOLVER.ADR.ExRecipNotFound; Recipient not found by Exchange Legacy encapsulated email address lookup

• It only fails when the recipient comes from auto-complete, an old message (especially one imported from PST) or an existing meeting.
• The recipient was recently deleted and recreated, restored into a new account, or migrated from another organization or forest.

Why it happens#

Every Exchange recipient has a LegacyExchangeDN, an X.500-style name such as /o=Contoso/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=…-jsmith. Outlook and Outlook on the web store internal recipients in the auto-complete cache by this value rather than by SMTP address. Stored messages and meeting attendee lists do the same.

When you delete and recreate the user, or move the mailbox content into a new object with a PST import or a third-party tool, the new object gets a new LegacyExchangeDN. Old references then point at a name that no longer exists. Transport wraps the unresolvable value in an SMTP address (the IMCEAEX encapsulation: / becomes _ and special characters become +XX hex codes), the lookup fails, and the sender gets the 5.1.1 NDR. Microsoft also lists an outdated Offline Address Book as a cause.

Exchange matches an encapsulated address against LegacyExchangeDN and X500 proxy addresses. That's why adding the old value as an X500 address fixes it for everyone, including old items and meetings, without touching any client.

How to fix it#

1. Collect the failing IMCEAEX addresses#

Take the address from the NDR, or find every affected recipient at once with message tracking (useful after a migration):

Get-TransportService | Get-MessageTrackingLog -EventId FAIL -Start (Get-Date).AddDays(-7) -ResultSize Unlimited |
  Where-Object { $_.Recipients -like 'IMCEAEX-*' } |
  Select-Object Timestamp,Sender,@{n='Recipient';e={$_.Recipients -join ';'}} | Sort-Object Recipient -Unique

2. Decode it into an X500 address#

Microsoft's rules: remove the IMCEAEX- prefix and the @domain suffix, replace every _ with /, then turn each +XX into its ASCII character (+20 space, +28 "(", +29 ")", +2E ".", +5F "_"), and add X500: at the front. Do the underscore step first, so that an encoded +5F survives as a real underscore. This snippet follows those rules:

$ndr = 'IMCEAEX-_O=CONTOSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=4F1C0F0B7C2E4D6F9A8B1C2D3E4F5A6B-JSMITH@contoso.com'
$dn  = $ndr -replace '^IMCEAEX-', '' -replace '@[^@]+$', '' -replace '_', '/'
$dn  = [regex]::Replace($dn, '\+([0-9A-Fa-f]{2})', { param($m) [string][char][Convert]::ToByte($m.Groups[1].Value, 16) })
"X500:$dn"

Output:

X500:/O=CONTOSO/OU=EXCHANGE ADMINISTRATIVE GROUP (FYDIBOHF23SPDLT)/CN=RECIPIENTS/CN=4F1C0F0B7C2E4D6F9A8B1C2D3E4F5A6B-JSMITH

3. Add the X500 address to the current recipient#

Set-Mailbox -Identity jsmith -EmailAddresses @{Add='X500:/O=CONTOSO/OU=EXCHANGE ADMINISTRATIVE GROUP (FYDIBOHF23SPDLT)/CN=RECIPIENTS/CN=4F1C0F0B7C2E4D6F9A8B1C2D3E4F5A6B-JSMITH'}

Use the cmdlet that matches the object: Set-RemoteMailbox, Set-MailUser, Set-MailContact or Set-DistributionGroup, all with the same @{Add=…} syntax. Repeat for each distinct IMCEAEX value. A user who has been migrated more than once may need several X500 addresses.

4. Tidy up clients (optional)#

• Remove a single stale entry by selecting it in the auto-complete list and pressing Delete (or clicking the X). File › Options › Mail › Empty Auto-Complete List clears every entry, which users rarely appreciate.
• For Cached Exchange Mode, regenerate the OAB with Update-OfflineAddressBook -Identity "Default Offline Address Book", then have users download it from Send / Receive › Send/Receive Groups › Download Address Book.

Verify the fix#

Get-Recipient jsmith | Select-Object -ExpandProperty EmailAddresses | Where-Object { $_ -like 'X500:*' }

Allow time for Active Directory replication (and directory sync in hybrid). Then reproduce the original action: reply to the old message or pick the cached auto-complete entry. Good looks like this: the message arrives, and running the step 1 query again shows no new FAIL events for that IMCEAEX address.

Prevent it next time#

• Before you delete a mailbox that might be recreated, export its identity data:

Get-Mailbox -ResultSize Unlimited |
  Select-Object Name,PrimarySmtpAddress,LegacyExchangeDN,@{n='X500';e={($_.EmailAddresses | Where-Object { $_ -like 'X500:*' }) -join ';'}} |
  Export-Csv .\LegacyDN-backup.csv -NoTypeInformation -Encoding UTF8

• Where you can, restore the original account from the AD Recycle Bin, which keeps all of its attributes, instead of creating a new one. Moves inside the same organization don't change LegacyExchangeDN, because the AD object stays the same.
• In any migration that creates new objects (PST imports, third-party tools, cross-forest or tenant-to-tenant moves), stamp each source LegacyExchangeDN and every existing X500 on the target before users start replying to migrated mail. Microsoft calls out PST migrations as the most common culprit.
• Planning a hybrid move instead? See hybrid migration batches.

References#

• IMCEAEX non-delivery report when you send email messages to an internal user (Microsoft Learn)
• 550 5.1.1 RESOLVER.ADR.ExRecipNotFound when sending emails by using Outlook (Microsoft Learn)