Hybrid Exchange mrsproxy.svc connection closed

I'm getting this error:  The connection to the server 'ews.contoso.com' could not be completed. --->  Microsoft.Exchange.MailboxReplicationService.RemoteTransientException: The call to 'https://ews.contoso.com/EWS/mrsproxy.svc' failed. Error details: The underlying connection was closed: A connection that was expected to be kept alive was closed by the server. --> The underlying connection was closed: A connection that was expected to be kept alive was closed by the server.. ---> Microsoft.Exchange.MailboxReplicationService.RemotePermanentException: The underlying connection was closed: A connection that was expected to be kept alive was closed by the server. ---> Microsoft.Exchange.MailboxReplicationService.RemotePermanentException: The underlying connection was closed: A connection that was expected to be kept alive was closed by the server.

Nothing on Google helps at all!  I put in a call to Office 365 support and the tech was actually worse than not helpful about this issue.  At the start he mentioned that I would likely need to pay for a support ticket to get Exchange support.  He then gave me 'best effort' support which included telling me to change all of my EWS virtual directory authentication to basic from Integrated Windows authentication, which of course Exchange warns will break Outlook Anywhere.  That didn't fix it.  His suggestion was to export to PST, delete the whole AD account for the user, create a new AD account with all the same user information, create a new local mailbox, and finally import the PST.

I have Exchange 2013 and Exchange 2016 in my org.  They are behind a hardware load balancer.  I have recreated the Migration Endpoint in Office 365 to no avail.  Migrations were fine earlier this week.  They are now broken.  I have put the HLB into maintenance mode for two servers and I am only using one server to connect with for EWS hoping that would eliminate any persistence issues.  I changed the timeout value from the working fine before 60 seconds to now still not working 600 seconds.

I now have an open paid Exchange support ticket with Microsoft.  I will update this with findings/results.

On Prem Exchange support said it was an Office 365 issue.  After a week migrations just started working again.  No changes were made by me.

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.