Unable to bind to the destination server in DNS

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

then you can bypass dns to send your mail http://support.microsoft.com/default.aspx?scid=kb;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/Configuring_DNS_for_Exchange_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.

Dns does resolve properly and I can actually send a message from the command line.  However anything sent through via outlook or any type of client gets hunged in smtp queues.

Also
This customer claims that we are the only sender having this problem.

Try restarting your SMTP service.

Done that two-dozen times...  :)

Since you can send from the command line and not through email client, it would seem that the issue is within Exchange's DNS resolution--I assume you meant you sent from the command line was on the Exchange server having issues. If not, then try to send an email from that server.

Are the nameservers that Exchange is set to use for external resolution the same as the ones in the IP configuration (or are they the same in the server as on the machine you sent from command-line)? It is possible that something changed on the forwarding DNS server or that something is cached in DNS, so what happens if you change the forwarder in exchange to a different nameserver? If your ISP has more than one server, either move one of them up in the order or if you don't have them all listed, swap out for one that is.

Here's a link showing one way find/make the changes in Exchange 2000--I wasn't sure whether the server where SMTP was located was 2000 or 2003. It may or may not help:
http://www.msexchange.org/tutorials/Configuring_DNS_for_Exchange_2000.html

could you explain your DNS setup.
How is your exchange server set to use DNS ?
Any errors in the event viewer ?

Create an SMTP connector for the destination domain and try to send the message.

Yes, I sent the message from the command line on that Exchange server.
 
The Exchange server uses two internal DNS servers that have a number of forwarders listed for external resolution.  I tested all of these forwarders, and every one of them resolves the name properly.

Your suggestion worked!!!!
Thanks