Exchange contact NDR IMCEAEX NT5 00000000000000000000000000000000

Another bare bones post here.  I wish I actually understood WHY this happens.  What I do know is this does happen and here is my fix.

If you get a contact from another org you might end up seeing NDR errors that look like the following:

IMCEAEX-_o=NT5_ou=00000000000000000000000000000000_cn=...

When you get the NDR back it looks like the correct address is filled in in the message headers.  Only when you put your cursor over the person's name does the IMCEAEX address pop out.  This is what it looks like:

Delivery has failed to these recipients or groups:
LastName, FirstName
The email address you entered couldn't be found. Please check the recipient's email address and try to resend the message. If the problem continues, please contact your helpdesk.


Diagnostic information for administrators:
Generating server: mail.contoso.com
IMCEAEX-_o=NT5_ou=00000000000000000000000000000000_cn={32 char number}@mail.contoso.com
Remote Server returned '550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found'
Original message headers: ...

I don't know why, but appearntly it has something to do with a bad LegacyExchangeDN?

To fix it I run this command daily against my OU that the contacts are in:
Get-MailContact -OrganizationalUnit "OU=MailContacts,OU=OffSite,DC=ad,DC=mydomain,DC=com" | Update-Recipient



You may need to rebuild the OAB after doing this to solve the problem *right now* but I don't know.