Exchange 2010 to 2003 Mail Flow Issue

I'm currently having an issue where our exchange 2010 server is no longer sending emails to our Ex03 users. We currently changed the primary domain for email accounts on both Ex2010 & Ex2003 environments. When I send an email to a test account in my Ex2003 environment from a Ex2010 user account I get the following error from my delivery report tool:

3/12/2015 11:59 AM
The e-mail address for recipient "" was updated to the e-mail address "". The message is in the process of being delivered."

"The last attempt to send the message was at 3/12/2015 12:12:10 PM (UTC-05:00) Eastern Time (US & Canada) and generated the error '451 4.4.0 Primary target IP address responded with: "535 5.7.3 Authentication unsuccessful.." Attempted failover to alternate host, but that did not succeed. Either there are no alternate hosts, or delivery failed to all alternate hosts.'."
Martin EhrhardIT DirectorAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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.

AmitIT ArchitectCommented:
You need to enable anonymous setting on 2003. Check this.
Bill BensonPrincipal ConsultantCommented:
Does mail flow from 2003 to 2010? Do you have an RGC (routing group connector) from 2010 to 2003?
Will SzymkowskiSenior Solution ArchitectCommented:
primary domain for email accounts on both Ex2010 & Ex2003 environments. When I send an email to a test
Did you create a new Accepted Domain for this new SMTP domain? Also, did you create Email Address Policies for this new Accepted Domain and apply them to your users?

If you send an email from E2010 to another user with a E2010 mailbox does this work?

Also, try adding the Authenticated Users back to the SMTP Users Tab.

Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

Martin EhrhardIT DirectorAuthor Commented:
I do have an RGC setup between 2010 & 2003, this coexistence has been setup for a few months now without any issues. I feel as if there may be some weird issue with AD and authentication itself since I coincidentally ran into domain authentication issues with a SQL server.

The new domain is setup as an accepted domain and as the default. I did not create an email address policy for this added domain. But, emailing users within the Ex2010 environment works fine.

Are you referring to the receive connectors for modifying the authenticated users?
Will SzymkowskiSenior Solution ArchitectCommented:
Are you referring to the receive connectors for modifying the authenticated users?
Yes have you changed anything on the default receive connectors for Exchange 2010?

I did not create an email address policy for this added domain.
How do users get the email address if you did not create a policy to apply on the mailboxes?

Martin EhrhardIT DirectorAuthor Commented:
No change made to the default receive connectors for Ex2010. Once I added the domain to default policy in Ex2003 system manager the domain was available to all users including my Ex2010 users.
Will SzymkowskiSenior Solution ArchitectCommented:
Based on the error message it is clear that this is an authentication / permissions issue. Take a look at the below KB for additonal steps for Troubleshooting mail relay for Exchange 2003.

Search for 5.7.3 in the link below...

Martin EhrhardIT DirectorAuthor Commented:
Hello all,

Thanks for the suggestions. As it turned out the problem was due to a bad MS update (KB3002657) released on the 11th of this month (MS has acknowledged this update to have a bug). I removed this update on our domain & exchange servers. After uninstall everything went back to normal.

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
AmitIT ArchitectCommented:
Thanks for the update.
Martin EhrhardIT DirectorAuthor Commented:
MS support for directory services provided the fix to this problem.
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.