Exchange 2003 Server intermittent NDR issues. Bizarre, and can't track down.

I am having the hardest time tracking down an intermittent problem.  

I am running Exchange Server 2003 on a Server 2003 Standard installation which is also the Domain Controller.

Recently, we moved our DNS registration for our domain from Network Solutions to GoDaddy (ostensibly to "consolidate" a number of different domain names).  Ever since, we have been receiving intermittent, seemingly random NDR's generated by our server that give the following codes:

The following recipient could not be reached:
      USER NAME on 7/9/2009 10:25 am
          There was a SMTP communication problem with the recipient's e-mail server.  Please contact your system administrator.
          <mailserver.mydomain.local #5.5.0 smtp; 553 sorry, that domain isn't in my list of allowed rcpthosts (#5.7.1)>

The user who sent this e-mail (which was a reply with an attachment) sent another e-mail that was new to this same recipient and it went through 2 minutes later.  She then sent another reply (at my request) and IT went through, not 10 minutes after that.

I have also been getting these:

The following recipient(s) could not be reached:


      USER NAME on 7/6/2009 8:39 AM
            There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            <3dogkcntwolf.ThreeDog.local #5.5.0 smtp;530 authentication required for relay (#5.7.1)>

After the user re-sends this one, it goes as well.  So, the problem is intermittent, but it is happening often enough that it is causing serious issues, enterprise-wide.

Any ideas what this could be?
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.

Remote server is rejecting your connection for some reason. Or a possible issue with the remote server. NDR can be customized therefore may not tell you the exact reason.

To save your time, what I would suggest: before assuming things and taking action to correct this issue at your server. I would suggest you to contact remote email administrator to find out what is the exact cause of this issue. You may ask them to verify their inbound logs and provide the exact cause of rejection. Once you know the exact reason you can take necessary action to resolve it.

You can also refer the articles to get more details on MX records and to verify your configuration.
clenh2oAuthor Commented:

The e-mails that are being rejected are to many different parties.  The e-mail gets through upon a retry.  The failure appears to be transient at best.  I can never get the e-mail to fail the same way twice.  Occasionally, the same recipient will casue a NDR rejection to appear, but only days apart.  And again, upon resend, the e-mail goes through.  About one in every 150 e-mails or so is getting bounced.  Soem of these e-mails are in distribution groups, some are not.  Some are replies to e-mails they have received, others are original e-mails.

I have run the tests suggested.  Here are my results.    All MX are configured properly  No blacklist listings, 6.968 seconds - Warning on Transaction Time.  All passed.

So, one test sent a warning on Transaction Time, and it did it EVERY single time I ran the test.  Could this be a TTL thing?  Servers are timing out on replies?  But even so, why generate an authentication NDR?

Thanks in advance.

It is nothing related to TTL, It is the time taken to get a response from your server.. are you using tarpitting or some thing like that as a SPAM filtering techniques?
NDR May not tell you the exact reason since it can be customized. I would suggest you to enable SMTP logging to troubleshoot this issue. SMTP log can tell you something.
And as I said earlier, instead of assuming things just contact the remote admin and get the exact reason for failure and fix the issue.. This is what I do to fix such issues. :-)
Also check this post.. 

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
clenh2oAuthor Commented:
I am using tarpitting.  It is a time issue.  I verified this with SMTP logging and am getting time-out errors.  I did not contact remote admins as this was not an issue with their end.   Also, I found that GoDaddy places a bunch of default cnames in our domain control panel that are supposed to catch mail from alternate, likely addresses.  I removed these and this completely resolved my time-out issues.  There HAD to have been a DNS discrepancy, which now appears to be resolved.  I have not received a bounceback or a NDR in 29 hours.
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.