Introduction

A Microsoft 365 migration can move the mailbox successfully while replies to old messages still fail in Outlook. New mail may work, the user may already be fully cloud-based, and Outlook may look healthy overall, but reply chains keep targeting an old Exchange legacy address that no longer resolves correctly after the move.

Treat this as a recipient-history problem instead of a general mailbox outage. Start by checking whether the failure points to legacyExchangeDN, X500, or an IMCEAEX-style address, because those clues usually mean Outlook is replying to an old Exchange identity that was not preserved during migration.

Symptoms

  • Replying to older messages fails after Microsoft 365 migration
  • New messages to the same user work, but replies to existing threads bounce
  • NDRs mention IMCEAEX, X500, or an old Exchange-style address
  • Outlook auto-complete keeps selecting an obsolete internal address
  • The user’s mailbox is already in Microsoft 365, but reply history still breaks
  • The issue started after mailbox migration, cutover, or coexistence cleanup

Common Causes

  • The migrated mailbox is missing the old legacyExchangeDN as an X500 proxy address
  • Outlook cached an old Exchange recipient entry and keeps reusing it for replies
  • A mail contact, old remote mailbox object, or coexistence record still owns the legacy address
  • The mailbox moved, but historical address mappings were not preserved during migration
  • Shared mailboxes or renamed users lost one or more old Exchange identifiers
  • Cleanup removed legacy recipient objects before reply compatibility was verified

Step-by-Step Fix

  1. Capture the exact bounce or NDR generated by the failing reply and look for IMCEAEX, legacyExchangeDN, or X500 clues, because that tells you whether the failure is tied to an old Exchange identity rather than the current SMTP address.
  2. Confirm that sending a brand-new message to the user’s current Microsoft 365 address works, because that separates reply-history failure from a wider mailbox delivery problem.
  3. Check the migrated mailbox for the required historical X500 proxy addresses, because Outlook replies to old threads often depend on the old legacyExchangeDN still being present on the destination mailbox.
  4. Compare the failing legacy address with any old on-prem mailbox, contact, remote mailbox, or stale directory object, because a conflicting object may still own the identity Outlook is trying to reach.
  5. Add the correct X500 address to the intended mailbox only after confirming ownership, because you need to preserve reply compatibility without creating duplicate recipient conflicts.
  6. Clear or refresh Outlook auto-complete for the affected recipients if replies still target the wrong entry, because cached recipient history can continue using obsolete data even after directory fixes are made.
  7. Test replies from the original message thread and from Outlook auto-complete separately, because one path may be fixed while the other still uses stale recipient metadata.
  8. Check similar users, renamed mailboxes, and shared mailboxes migrated in the same batch, because missing X500 history often affects more than one recipient after Exchange cleanup.
  9. Document which historical X500 addresses were restored and why, because reply-chain compatibility is easy to overlook during future Microsoft 365 migrations and directory cleanup.