PermanentlyClearPreviousMailboxInfo WARNING: The command completed successfully but no settings of 'user' have been modified.

 I'm going to take one for the team on this...

So you have hybrid Exchange and Office 365 and for some reason you wind up with an account with a local Exchange Mailbox and an Office 365 mailbox.  After years of just delete the whole Office 365 account to fix the issue Microsoft finally gave us this:

Permanently Clear Previous Mailbox Info: https://blogs.technet.microsoft.com/exchange/2018/01/17/permanently-clear-previous-mailbox-info/

Great!  That's awesome!  I have a user right now that I need to fix.  Wonderful.  Glad I remember seeing that somewhere along the way.

{The actual command most people would use would be Set-User, but I use the O365 prefix to my Office 365 powershell commands so as to not clobber my local AD and Exchange powershell commands. -ED}
PS C:\Scripts\Exchange 2013> Set-O365User user@contoso.com -PermanentlyClearPreviousMailboxInfo

WARNING: The command completed successfully but no settings of 'user' have been modified.

What?  Why not?

Why is Google only telling me of other people who are seeing this same error but now resolution?

Open support ticket.  DELAY DELAY DELAY

Oh wait that user has an Exchange online license. Let's unselect that.

PS C:\Scripts\Exchange 2013> Set-O365User user@contoso.com -PermanentlyClearPreviousMailboxInfo


PS C:\Scripts\Exchange 2013>

Uhhhhhhhhhh...  Genius!  Well DUH!  So there you are.  I'm admitting that I made a pretty stupid mistake so you can read this and then not have to admit to anyone else that you did.

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.