ROUTING FAILED: {[{LRT=};{LED=550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found};{FQDN=};{IP=}]}

I came across this error after recently migrating a user mailbox - I was told by the user that they had sent an email to another couple of users and one specific user did not receive the email. What added to the perplexity of the situation was that there was no NDR generated by Exchange to the sender either.

So I decided to hit up the mail logs with Get-MessagingTrackingLog:
Get-MessageTrackingLog -Server MS02 -Start "03/26/2015 06:00:00" -End "03/26/2015 08:00:00" -Sender "user@domain.com"  -MessageSubject "Your subject title" | FL

and was interested to find out that there was a ROUTE event that had a status of 'FAIL':

In the end it was only by chance I stumbled upon the issue - it was in fact that when a user is migrated (even from one mailbox to another to another environment / domain) there X400 address changes - the problem lies in the fact that this X400 (or X500, X800) data is held within a users NK2 data and because it does not automatically update with the new X400 address (coupled with the fact that Outlook uses the X400 address to route mail by default - not the SMTP address!) the mail was being sent to the users old x400 address!

In order to resolve this you can manually modify all of the end user's NK2 files (yikes) or alternatively add the old x400 address under the mailbox properties. In order to do the latter you will firslty need to get hold of the old X400 address - fortunately when you migrate a mailbox from one DB to another the original DB retains the mailbox (for 30 days by default) in a disconnected state - so we need to run the following command on the mailbox database with the original (now disconnected) mailbox on:

or if you have access to the original mailbox still you can use:

Get-Mailbox <user-mailbox> | fl LegacyExchangeDN

I have also encountered this issue where the migration process has stripped the X400 address from the mailboxes email addresses.

We finally add the additional X400 (or X500, X800) address to the user's email addresses in ECP > Recipients > Properties > Email Addresses > Add.

The X400 (or X500, X800) address should look something like:
/o=org/ou=Exchange Administrative Group/cn=Recipients/cn=Joe Bloggs