NDR after removing a recreating a mailbox - Exchange 2013.

We are running Exchange 2013 with a Windows 2012 Domain Controller.
The on-premises I.T person did the following:
1.      Created Active Directory account.
2.      Created an Exchange mailbox and associated it with the AD account.
3.      Now, this is where things went awry.  The I.T admin deleted the mailbox, and then created one again.
Now when users email the user, they received an NDR message – please see below.
I know that certain times like this, an X500 address needs to be created or edited, or at least I think that’s the case.
Any suggestions?

From: Microsoft Outlook
Sent: Thursday, March 03, 2016 7:56 AM
To: IT Person
Subject: Undeliverable:

Delivery has failed to these recipients or groups:
John Barnett
The email address you entered couldn't be found. Please check the recipient's email address and try to resend the message. If the problem continues, please contact your helpdesk.

Diagnostic information for administrators:
Generating server: CTC-MAIL-MBX.CTC.local
Remote Server returned '550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found'
Original message headers:
Received: from CTC-MAIL-MBX.CTC.local ( by
 CTC-MAIL-MBX.CTC.local ( with Microsoft SMTP Server (TLS) id
 15.0.1156.6; Thu, 3 Mar 2016 07:56:06 -0800
Received: from CTC-MAIL-MBX.CTC.local ([fe80::dd7:2c6f:6495:53d5]) by
 CTC-MAIL-MBX.CTC.local ([fe80::dd7:2c6f:6495:53d5%12]) with mapi id
 15.00.1156.000; Thu, 3 Mar 2016 07:56:06 -0800
Content-Type: application/ms-tnef; name="winmail.dat"
Content-Transfer-Encoding: binary
From: IT Person <ITPerson@domain.com>
To: John Barnett <ProblemUser@Domain.com>
Thread-Index: AdF1ZTHl7RzWqpJ0Q+OC6UZcT5m0xg==
Disposition-Notification-To: IT Person <ITPerson@domain.com>
Date: Thu, 3 Mar 2016 07:56:06 -0800
Message-ID: <5d31037d3e9c407cb59b1a9121fb4d87@CTC-MAIL-MBX.CTC.local>
Accept-Language: en-US
Content-Language: en-US
X-MS-TNEF-Correlator: <5d31037d3e9c407cb59b1a9121fb4d87@CTC-MAIL-MBX.CTC.local>
MIME-Version: 1.0
X-MS-Exchange-Transport-FromEntityHeader: Hosted
X-Originating-IP: []
Return-Path: ITPerson@domain.com

Thanks in advance.
Who is Participating?
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.

Matt MinorTechnical Systems AnalystCommented:
Is the NDR being received by all users attempting to send to this address? I suggest trying to send a message by typing the full email address into the TO field in outlook (avoid using cached entries) and see if it is delivered.

Certainly sounds like the IT admin is using a cached entry which would contain incorrect X500 values.

Off the top of my head.

When the new mailbox was created for the existing user account, was there an email address policy in place that was overridden (by unchecking the box in the mailbox properties) causing the emails to have say fred.blogs@contoso.local instead of fred.blogs@yourdomain.com?

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
realtimerAuthor Commented:
Hi -

No such policy in place.  The issue appears to have corrected itself.  Perhaps Offline Address Book got updated individually and rectified the issue.  

Unfortunately I don't have symptoms anymore to prepare for future occurrence of the issue.  

Thanks for now.

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.