Recipient not found by Exchange Legacy encapsulated email address lookup

What’s up with this message: “Recipient not found by Exchange Legacy encapsulated email address lookup”? This problem started with someone working in an organization where they were migrating from a Microsoft Exchange 2007 to Exchange 2016 environment.

I was called in to take a look at the problem when one of the employees of the company started experiencing problems when sending emails internally. Let’s say the name of the company is tipsdotcom.com (Not using the actual name of the company here to protect their privacy).

They had just migrated from a Windows SBS 2008 server with Active Directory and Microsoft Exchange 2007 to a Windows Server 2016 Standard with Active Directory and Exchange 2016.

There is no direct migration path from Microsoft Exchange 2007 to 2016, so either you need to migrate to Exchange 2010 first and THEN to Exchange 2016, OR you can export all mailboxes on the client-side (.pst files), decommission the old Exchange server, re-create the mailboxes on the new Exchange 2016 server and import the mailboxes. The people at tipsdotcom.com decided to take the second approach. Which is a viable option, except that you need to pay attention when re-creating the mailboxes in Exchange 2016, or you’ll get in trouble when sending mails internally (to other recipients @tipsdotcom.com that is).

Indeed, sending mail to people OUTSIDE their organization was no problem, as well as receiving mail from the outside world. Indeed, it was when emailing internally that people sometimes got NDR (non delivery report) error messages when they were sending emails to colleagues on the company network. Yup, sometimes, but I’ll get to that in a minute. First let me document the entire exact error message here, so you can match it with your own situation.

The Entire “Recipient not found by Exchange Legacy encapsulated email address lookup” Message

Here is the entire IMCEAEX NDR message that people got when sending emails to colleagues:

Delivery has failed to these recipients or groups:

'Meeusen William'
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 email admin.

In addition to that, there was also this blurb of information “for administrators”:

Diagnostic information for administrators:

Generating server: tdcsrv03.tipsdotcom.local

IMCEAEX-_O=FIRST+20ORGANIZATION_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=WILLIAM@tipsdotcom.local
Remote Server returned '550 5.1.11 RESOLVER.ADR.ExRecipNotFound; Recipient not found by Exchange Legacy encapsulated email address lookup'

I have included the above so you can check whether or not your own message matches the one described here, so if you are reading this to fix your own IMCEAEX NDR problem, you can assess if you’re on the right track.

Anyway, the reason why this happens is because the existing mailboxes were removed during the decommissioning of the Microsoft Exchange 2007 server and subsequently new mailboxes (with the same email addresses) were created in the Microsoft Exchange 2016 server, which was running on the new Windows Server 2016 domain controller machine. The Active Directory was migrated away from the old Small Business Server 2008 R2 to the new Server 2016, but as mentioned above, there is no direct migration path from Exchange 2007 to Exchange 2016. Hence the removal and re-creation of the mailboxes.

As these new mailboxes are created, they do get the same email addresses as before (on the SBS 2008 server), but actually they are not entirely the same. After recreating all the mailboxes on the new Exchange 2016 server, imports of the old .pst files have been done to restore the contents of the mailboxes on the client-side and that is where the trouble originates. Along with the e-mail messages in the inboxes, information about the sender is also restored in the inbox.

The solution lies in adding the correct X.500 email addresses in the accounts on the new Exchange 2016 server.

Adding X.500 Email Addresses to Stop IMCEAEX NDR Messages

In order to find out exactly which X.500 email addresses, we need to take another look at the error message:

IMCEAEX-_O=FIRST+20ORGANIZATION_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_[email protected]

This fragment contains all the information we need to be able to add the X.500 email address to the account. But it needs some reformatting.

You’ll not that the string of text contains a few characters that need to be replaced before you can use them to paste the information in the X.500 email address (I’ll get to HOW you need to do that in a minute). I have marked them in red in the string above.

The characters that need to be replaced are:

_ (underscore) needs to be replaced by / (forward slash)
+20 needs to be replaced by a SPACE
+28 needs to be replaced by ( (opening parenthesis)
+29 needs to be replaced by ) (closing parenthesis)

So, after replacing everything, you would get something that looks like this:

IMCEAEX-/O=FIRST ORGANIZATION/OU=EXCHANGEADMINISTRATIVEGROUP(FYDIBOHF23SPDLT)/CN=RECIPIENTS/[email protected]

All would have to be in one line, but your web browser probably breaks the thing up in multiple lines of text.

Now that you have carefully replaced all the necessary characters, it’s time to cut off the IMCEAEX- part at the beginning of the string, resulting in this:

/O=FIRST ORGANIZATION/OU=EXCHANGEADMINISTRATIVEGROUP(FYDIBOHF23SPDLT)/CN=RECIPIENTS/[email protected]

Now that you have created the correct string to add to the recipient’s Exchange account, go to the Exchange Administrative Center, click on recipients, then mailboxes and select the account for which you want to add the X.500 email address.

If you then click on the pencil icon to edit the account, you can go into the account details and select email address and click the + sign.

Then, select the radio button for a custom address type, enter X500 in the address type field and paste the string you’ve constructed above into the address field.

Then click ok and save the changes.

That should fix the problem mailing internally to co-workers for you.

Sending Email Internally Sometimes Fails

With all of the above said, I should also add that the symptoms (before you implement the fix) will appear “randomly”. By that I mean that sometimes you WILL be able to send an email internally and sometimes it will not work. For instance, when you create a NEW email message and type the email address of the recipient manually, Exchange will be able to deliver the message and everything will look fine. But when you REPLY to a message or let Outlook work with the autocomplete list when entering the destination email address, THAT is when you’ll get the error message bounce back. That is because in that instance, Exchange will try to work with the “old” X500 email address, living in the imported .pst file that you used to restore the mailbox contents.

When I was working on fixing this problem, I encountered a few blog posts on the internet where the solution described above was also presented, but in one of the posts that I found, an error was introduced somewhere during a copy/paste operation of the X500 string. Once a useful solution to a common problem is published somewhere on the internet, you’ll often find other forums or blogs where people are discussing the same problem, with links to the original article to help others solve their issue.

During my work on this, I also came across a comment from someone who mentioned that he had wasted 8 hours trying to figure things out, due to the copy/paste error in the construction of the X500 string.

That’s why I decided to publish my own version of the issue so hopefully it can save someone some time and frustration trying to implement this fix.

If you like this article or find it helpful, please consider giving it a thumbs up or brief comment in the section below. And please don’t hesitate to link to it if you’re participating in a discussion online about the topic. I’d appreciate that a lot, thanks!