We recently moved our users to new Exchange servers and have been seeing intermittent bouncebacks after going through our relay provider. We're not on any blacklists, nor blocked by external recipients SPAM provider. Our relay provider is having trouble figuring out why this is happening. Some intermittent bounceback examples:

- user reply's to external recipient message and gets bounceback

- users sends a single email with multiple recipients in the same domain and gets a bounceback from one of the users

- user gets bounceback from an external user he has mailed successfully many times before (and even within the hour)

Running Exchange 2010 SP3 RU8. All mail flows from the same IP and configuration (we moved from physical servers to virtual but the virtual have new name and IP). We're setup correctly with our Relay with login and have updated our SPF record. 99.99% of external mail goes through fine. I can see our message gets handed to our relay provider. 

Any suggestions or ideas on what to look at appreciated.

Hi Hoover

Following things can be done

1) First run EXBPA to check if we get any misconfig errors ( just a check )

2) Go through your event logs to see if we get any clue.

3) Do a telnet to your relay provider and see if everything is fine and also suggest your relay provider to to a telnet test to those affected domains and see the results

4) Enable protocol loggin both send and receive and see if you are able to track anything

5) Enable message tracking for those  nondelivery mails and see if you get where the message gets dropped.

6) You can  Message header of the NDR to see in which hop the email was dropped 

Also it would be great if you could provide us the NDR so that we can try to figure the issue 

Hi,

Great checklist from Sathish.

As Sathish mentioned, NDR without sensitive information is helpful for the further troubleshooting.

How about re-sending the bounced email?

Thanks

If you have feedback for TechNet Subscriber Support, contact tnmff@microsoft.com

Wow. Great reply and very much appreciated. I'm looking through all your checks now. 

Here is an NDR that we recently got. Immediately resending the message always seems to be successful.

Delivery has failed to these recipients or groups:

 user1@maildomain.com Your message wasn't delivered due to a permission or security issue. It may have been rejected by a moderator, the address may only accept e-mail from certain senders, or another restriction may be preventing delivery.

 user2@maildomain.com Your message wasn't delivered due to a permission or security issue. It may have been rejected by a moderator, the address may only accept e-mail from certain senders, or another restriction may be preventing delivery.

 The following organization rejected your message: maildomainXXX.mail.protection.outlook.com.