Exchange 2013 users receiving NDR from user within same organization

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.

Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Does it happens to all internal emails sent to this recipient or just some?  If just one then my guess is that the autocomplete in the sender's outlook still points to the old X500 address.  In this case just simply delete that autocomplete entry then retype the email address then send and it should work.

In case where a lot of senders in the organization can't send to this one recipient then you will have to add the entry for the affected mailbox account.
timgreen7077Exchange EngineerCommented:
The internal users don't email based on smtp addresses, outlook actually emails based on the x500 address. You can 1 of 2 things:

1. the internal user will need to delete the old email address from their autocomplete cache in outlook and the manually retype the address or grab it from the GAL. That will resolve it.

2. you can get the failed email that is generated, and it will should an address that looks like this:"IMCEAEX-_O=EXCHANGELABS_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT"

you will need to convert this address correctly and then add the converted address to the email proxy addresses on the newly created mailbox that was deleted and then recreated. see the below link to show you how to convert this address and add it to the user so that other users that email him will be able to successfully email without the need to clear that address from the autocomplete cache.

clearing the address from the autocomplete cache in outlook is the quickest way though.
Similar solution provided.
Simplify Active Directory Administration

Administration of Active Directory does not have to be hard.  Too often what should be a simple task is made more difficult than it needs to be.The solution?  Hyena from SystemTools Software.  With ease-of-use as well as powerful importing and bulk updating capabilities.

Riaz Alexander AnsaryEnterprise Infrastructure Systems EngineerCommented:
As guys mentioned above its the X500 issue. I have written an article about this that will guide you step by step on how to resolve this.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
JamesNTAuthor Commented:
Thank you all.
JamesNTAuthor Commented:
Thank you.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.