Exchange Error: 550 5.1.1 RESOLVER.ADR.ExRecipNotFound

Sometimes you have a reason to restore a mailbox from back-up, because it was deleted by mistake or a former employee is hired again. But after restoring the mailbox, several (internal) users are not able to send email to the restored mailbox and receive an error message like: Delivery has failed to these recipients or groups. With the error code IMCEAEX #550 5.1.1 RESOLVER.ADR.ExRecipNotFound ##
In other Exchange versions the message also contains Recipient not found by Exchange Legacy encapsulated email address lookup.
(This message could also show up after migrating the mailbox to another forrest)

The first thing you probably think of to resolve the issue, is to delete the cached email address from Outlook, but that did not resolve the error message.

We just created a new account, with an old, restored mailbox, maybe we need to restart the MS Exchange Active Directory Topology service (or even the Exchange server). In this case, that did not work either.

So what is the solution to this problem!? I was pointed at this blog (credits to the writer of that blog!). It was the same error code we received, but not the exact same message (Recipient not found by Exchange Legacy encapsulated email address lookup is missing from our message) but that makes no difference. It pointed me in the right direction, the LegacyExchangeDN was changed since we created a new account/ restored the mailbox and was not associated with the new account.

Exchange internally still uses an X.500 addressing schema. So when an user sends an email internally to the restored mailbox, the old X.500 address is used and therefor Exchange is not able to deliver the email. The user who send the email receives a Non Delivery Report (NDR) with the old ID in the form of a IMCEAEX address.

We are able to rebuild the required X.500 address based on the received IMCEAEX in the NDR by using a PowerShell script.
Copy below PowerShell scipt:

$Direction = Read-Host “Ingrese IMCEAEX”
$Remplazo= @(@("_","/"), @("\+20"," "), @("\+28","("), @("\+29",")"), @("\+2C",","), @("\+3F","?"), @("\+5F", "_" ), @("\+40", "@" ), @("\+2E", "." ))
$Remplazo | ForEach { $Direccion = $Direccion -replace $_[0], $_[1] }
$Direccion = “X500:$Direccion” -replace “IMCEAEX-“,”” -replace “@.*$”, “”
Write-Host $Direction

Open PowerShell ISE and past the script.

Click on the Play button to run the script and it will now ask you to enter the IMCEAEX, which you received in the NDR. It starts with IMCEAEX and ends with the domainname. 

Paste it in the PowerShell window and press ENTER. You now receive the X.500 address.

The last step is to enter the received X.500 address to the restored mailbox. You can do that by opening the user account from ADUC, on the Attribute Editor tab go to proxyaddress.

Click on Edit and paste the X.500 address in the Value to add box, click on Add and OK (twice)

It is also possible to add the X.500 address to the mailbox by using the Exchange; In Exchange 2010 you can use the Exchange Management Console. In Exchange 2013 and 2016 you can use ECP.
On the e-mail addresses tab you enter the X.500 address (below is a print screen from Exchange 2010)

After adding the X.500 address, we are now able to send internal e-mail to the restored mailbox!