Unable to bind to the destination server in DNS

I have a win2k server with multiple domains on it many of which have a generic contact us page with a form that when submitted calls an .asp page that utilizes CDONTS. These pages have worked extremely well in the past until a couple days ago when all of a sudden every time that page is called i'm getting event 4000 in source smtpsvc Message delivery to the remote domain 'mydomain.com' failed for the following reason: Unable to bind to the destination server in DNS.

The mail just gets dropped into the queue and eventually into badmail. I've found lots of other people on the web who have encounter similar problems but have found no solution yet. I've restarted SMTP, restarted DNS client, restarted the server,
everything, played with settings and still am getting this error. Which is bizarre because it was working great until out of nowhere it
fails for an unknown reason.

Any advice or opinions on what I could try to fix this would be much appreciated.

Look at the following article: http://support.microsoft.com/kb/924251

What is the other mail system for external users? Is it also running on Exhcange 2000/2003 and what operating system? Details of mail system where external users are hosted are very important to find a solution to this problem. If a mail system is running Exchange 2000/2003 on Windows 2000 and if SMTP or IIS is been re-installed then you would see this problem. Look at the following article if above description is true: http://support.microsoft.com/default...;en-us;q290290

Try a manual telnet test on port 25 from your Exchange server to the IP address of one of the destinations you can't send to. Let me know if you need assistance on the SMTP commands within the telnet session.

Have you by any change configured "external DNS servers" on the properties of the SMTP virtual server in the exchange system manager? If so, remove them.

can you telnet to the mail server yourself? This will let us know if it is an dns issue. http://support.microsoft.com/default...b;en-us;153119

then you can bypass dns to send your mail http://support.microsoft.com/default...;en-us;q285863

It means that you are having problem to resolve the destination domains IP address. Check your DNS settings on the exchange server. The site below will help you

http://www.msexchange.org/tutorials/...ange_2000.html

Use nslookup to resolve the destination domain from your PC.

It might also be possible that their DNS record have become Obsolete. Go to http://www.dnsreport.com and make a mail test to the destination domain.