I have a strange situation.  I had a user who setup loads of Outlook Rules, and corrupted his iPhone which was connected with ActiveSync.  The only way to get the iPhone to work again was to delete the entire Exchange email account, and start over.  That in turn has created another problem.  Users on the Exchange Server can reply to emails from the account, but cannot send emails from scratch.  They have tried using autocomplete, typing the email address in manually, and using the address book.  Here is an error message:

Delivery has failed to these recipients or groups:

Our Employee
The e-mail address you entered couldn't be found. Please check the recipient's e-mail address and try to resend the message. If the problem continues, please contact your helpdesk.

Diagnostic information for administrators:

Generating server: EXCHANGE.dc1.contuso.com

IMCEAEX-_O=CONTUSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=Our+20Employee02c@contuso.com
#550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##

Original message headers:

Received: from EXCHANGE.dc1.contuso.com ([0.0.0.0]) by

 Exchange.dc1.contuso.com ([0.0.0.0]) with mapi id 14.01.0438.000; Fri,

 24 Jul 2015 12:46:58 -0700

Content-Type: application/ms-tnef; name="winmail.dat"

Content-Transfer-Encoding: binary

From: Our Employee2 our.employee2@contuso.com

To: Our Employee

        <IMCEAEX-_O=CONTUSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=Our+20Employee02c@contuso.com>

Subject: testing2

Thread-Topic: testing2

Thread-Index: AdDGStCu6coxF6TUTLC2mS2k1xJvyw==

Date: Fri, 24 Jul 2015 12:46:56 -0700

Message-ID: <11E6675B7544C049B8B6FEC4ED0255E44BD51878@Exchange.dc1.contuso.com>

Accept-Language: en-US

Content-Language: en-US

X-MS-Has-Attach: yes

X-MS-TNEF-Correlator: <11E6675B7544C049B8B6FEC4ED0255E44BD51878@Exchange.dc1.contuso.com>

MIME-Version: 1.0

X-Originating-IP: [0.0.0.0]
Also I am able to send emails to this account from outside the domain.  
Any assistance would be appreciated.
Michael

• Edited by Michael1000 Monday, July 27, 2015 7:29 PM

I found this article that described how to fix this step-by-step using the Microsoft Exchange Management Console by adding an X500 email address to the account.

https://www.simple-talk.com/sysadmin/exchange/exchange-e-mail-addresses-and-the-outlook-address-cache/

The only part missing from this article was copying and pasting the following from the bounce message to get the old X500 address into the new address to be added to the user's account:

_O=CONTUSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=Our+20Employee02c@contuso.com

Then change "_" to "/", +20 to space, +28 to (, +29 to ), and remove the @domain off the end.  This is described in this article as Hamit kindly referenced.

https://support.microsoft.com/en-us/kb/2807779

Then enter X500 in the E-mail Type field.  Click OK a couple times, and you are ready for testing.

Michael

• Edited by Michael1000 15 hours 12 minutes ago
• Marked as answer by Amit TankMVP, Moderator 12 hours 9 minutes ago

Great, glad you figured out how to go over

I found this article that described how to fix this step-by-step using the Microsoft Exchange Management Console by adding an X500 email address to the account.

https://www.simple-talk.com/sysadmin/exchange/exchange-e-mail-addresses-and-the-outlook-address-cache/

The only part missing from this article was copying and pasting the following from the bounce message to get the old X500 address into the new address to be added to the user's account:

_O=CONTUSO_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=Our+20Employee02c@contuso.com

Then change "_" to "/", +20 to space, +28 to (, +29 to ), and remove the @domain off the end.  This is described in this article as Hamit kindly referenced.

https://support.microsoft.com/en-us/kb/2807779

Then enter X500 in the E-mail Type field.  Click OK a couple times, and you are ready for testing.

Michael

• Edited by Michael1000 Friday, July 31, 2015 4:15 PM
• Marked as answer by Amit TankMVP, Moderator Friday, July 31, 2015 7:19 PM