After deleting and recreating a user’s mailbox certain internal user’s were faced with error #550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ## when attempting to send mail to the user.
The reason and solution as to why this error was received is in this article
https://www.simple-talk.com/content/print.aspx?article=628
I needed to add a X.500 email address to the recipients mailbox in order for message to get to his mailbox.
The X.500 address of a message sender can be retrieved using a tool such as Microsoft Exchange Server MAPI Editor to open a message and get the PR_SENDER_EMAIL ADDRESS property:
The addess is added using these steps in Exchange Management Console
Frank's Tech Blog 