I have seen this issue on various client sites. When new users are created and an email sent to the new users email address then following error occurs.
Remote Server returned '550 5.1.1 RESOLVER.ADR.RecipNotFound; not found
When logging into OWA as the new user account you also see the following error.
You will however find that no errors occur when emailing existing mailboxes in your environment. The issues above are caused by Domain Controllers not replicating successfully. You can force a replication of all Domain Controllers in your environment with the following command ran from a DC.
This may take some time depending on the size of you Active Directory. Thats the easy fix, you may find that the command above shows errors between your Domain Controllers. In this situation you can run the following command to see specifically where domain replication is failing.
repadmin /showrepl *
Once you have identified the domain controller that cannot replicate I would advise you then check the event logs within that server for any obvious hints of why replication is failing. You can also reference the Microsoft article below.