email can't be delivered to valid recipient address

Hello. I have a problem with email to a business partner that we have been sending stuff to for years but suddenly all our email is bounced back as non-deliverable. I have been talking with them and they say nothing has changed of their end. Nothing has changed on our end for certain. It's only email from us to them that gets rejected (tested with yahoo email and it works fine) and we are able to recieve from them. Has anyone run into a similar situation before?

We have microsoft exchange 2000 (latest SP and patches). The smtp message queue properties say that a smtp protocol error has occuredd but donesn't specify any additional info. Below are copies of the error messages I have received while testing:

 The destination server for this recipient could not be found in Domain Name Service (DNS).  Please verify the email address and retry.  If that fails, contact your administrator.
            < #5.4.0>

Could not deliver the message in the time limit specified.  Please retry or contact your administrator.
            < #4.4.7>

The e-mail system was unable to deliver the message, but did not report a specific reason.  Check the address and try again.  If it still fails, contact your system administrator.
            < #4.0.0 smtp;417 DNS lookup failure:  Try again later.

Any ideas?
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.

David WilhoitSenior Consultant, ExchangeCommented:
Looks like they've played with their DNS servers recently, I actually did a lookup and their records showed internal IP addresses. What a mess!

Clear the DNS cache on your DNS servers, or, delete the cached entry for that domain. REstart the DNS server service, and client service. On the exchange server, run ipconfig /flushdns, and then retry the messages.


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
SirTravisAuthor Commented:
I shall try it

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.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.