Exchange 2013 with the latest CU.
There was a situation where an Exchange mailbox was accidentally deleted. This, of course, also deleted the AD account (why MS does this is beyond me). So the AD account was recreated and a new mailbox made. The user's email was recovered to a PST file from backup. So all is good.
When the new mailbox was created, the wrong alias was used so the alias was changed. As of now the user can send and receive emails from the outside world. However, the user cannot receive emails from within the organization. When someone within the organization tries to email the user, an NDR is generated.
'550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found'
The user clearly has a mailbox that works with the outside world. What can be done to fix getting this NDR from coworkers within the same org?
NOTE: This mailbox was not migrated from another org or from a previous version of Exchange. All searches on the Internet point to migrations being the cause which is not the case here which is why I am posting on EE.