Exchange 2003 SP2 Intermittently tells it's own users Relaying Denied

Here's an odd problem.  Running SBS2003 SP2 with Exchange 2003 SP2.  A user just received the following yesterday:

Your message did not reach some or all of the intended recipients.
      Subject:  RE: XXXX
      Sent:     1/30/2008 12:16 PM
The following recipient(s) could not be reached:
      'Remote Recipient' on 1/30/2008 12:17 PM
            You do not have permission to send to this recipient.  For assistance, contact your system administrator.
            <localdomain.com #5.7.1 smtp;550 5.7.1 <recip@remotedomain.com>... Relaying denied>
      'Remote Recipient 2' on 1/30/2008 12:17 PM
            You do not have permission to send to this recipient.  For assistance, contact your system administrator.
            <localdomain.com #5.7.1 smtp;550 5.7.1 <recip2@remotedomain.com>... Relaying denied>

User is setup to use Microsoft Exchange with no additional POP/SMTP profiles setup, so their Outlook client only talks to the Exchange Server.  The Exchange server kicked back an NDR stating that the user in the local domain doesnt now have permission to send to the recipient.  Looking at the SMTP log, it appears that it didnt even attempt to send the message to the SMTP connector, as the only references to the recipient e-mail was the second attempt, where the e-mail then went through.  The only thing different the local user did the second attempt was put the recipient addresses in the TO field instead of the CC field.

Anyone have any ideas on this.  I have another user who has reported this issue as well, and a second attempt at sending the e-mail is usually successful.

LVL 1
forthphazeAsked:
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.

cedarghostCommented:
This is typically cause by bad DNS settings, recipient policies having updating problems or SMTP being blocked at some point. In your case it is probably not your SMTP connector but something stopping the mail from getting to that point. Now I see you are getting a 5.7.1 errorand that indicates a problem with your Recipient Policy. Take a look at this article for some initial troubleshooting steps for this problem:
http://searchexchange.techtarget.com/generic/0,295582,sid43_gci1222337,00.html
0

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
forthphazeAuthor Commented:
I've read through everything on the link you posted above, and would agree that of all the scenarios theorized in the webpage, RP or message routing would have to be the likely cause.  Looking at the following:

http://technet.microsoft.com/en-us/library/aa997788(EXCHG.65).aspx

It's evident that the error was produced in the Exchange MTA, because I do see both messages in the MTA log, but only the successful send attempt in the SMTP log.  I also found this link regarding the event ID codes:

http://support.microsoft.com/kb/821905

And it appears that the Exchange server got confused and tried to send to the wrong MX.  There were three recpients in the e-mail, two of one remote domain, one of another remote domain.  The Exchange server attempted to send the message to all three recipients to the remote domain that only hosted one of the recipients.

Three months ago I removed Symantec MS for Exchange and IHateSpam, I'm guessing there's a correlation to this problem and those un-installs.

Since your link referenced DNS and MX errors, and led me to my answers, I'll award the points.
0
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
Microsoft Legacy OS

From novice to tech pro — start learning today.