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

You need to add legacyExchangeDN of old account as an x500 address of current mailbox.

/o=Contoso/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=Our Employee

Look for the Method-2 in below KB just to Create an X500 proxy address for the old LegacyExchangeDN attribute for the user---- https://support.microsoft.com/en-us/kb/28077