Undeliverable Message (NDR): 554 5.4.4 SMTPSEND.DNS.NonExistentDomain; nonexistent in Exchange 2007

A client is in regular contact with a vendor in Thailand but is unable to respond to their emails.  When he sends a message, the sender gets an Undeliverable reply email.  I ran the destination domain on mxtoolbox and did an nslookup from the server, both appear correct.  Here is the Diagnostic info from the email:

Diagnostic information for administrators:
 
Generating server: mydomain.local
 
user1@destination-dommain.co.th
#554 5.4.4 SMTPSEND.DNS.NonExistentDomain; nonexistent domain ##
 
user2@destination-dommain.co.th
#554 5.4.4 SMTPSEND.DNS.NonExistentDomain; nonexistent domain ##
 
Original message headers:
 
Received: from mydomain.local ([fe80::88d8:9e4f:80fe:1263]) by
 mydomain.local ([fe80::88d8:9e4f:80fe:1263%11]) with mapi; Wed, 7 Jul
 2010 18:25:38 -0400
From: 
To: user1@destination-dommain.co.th, user2@destination-dommain.co.th
CC: 
Date: Wed, 7 Jul 2010 18:25:37 -0400
Subject: RE: AIR&SEA TAYLOR SHIPMENT
Thread-Topic: AIR&SEA TAYLOR SHIPMENT
Thread-Index: AcscLe0HSRzTTJ7MSMyErzLeawy6UQA140HAAAMvxIAALycQoAAQ2L5QAABwrAAAA9OK4A==
Message-ID: <16E4C46506C80C408151C30583ECBB1C1AAD6C2774@mydomain.local>
References: <6889177E25844B59ACC90064DFC2B8BE@SYNERGY21>
 <16E4C46506C80C408151C30583ECBB1C1AAD6C2283@mydomain.local>
 <EA05C8DC75CD4DCAB15DD09F55830DD0@SYNERGY21>
 <16E4C46506C80C408151C30583ECBB1C1AAD6C22EE@mydomain.local>
   <16E4C46506C80C408151C30583ECBB1C1AAD6C2747@mydomain.local>
 <16E4C46506C80C408151C30583ECBB1C1AAD6C274D@mydomain.local>
In-Reply-To: <16E4C46506C80C408151C30583ECBB1C1AAD6C274D@mydomain.local>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: multipart/alternative;
        boundary="_000_16E4C46506C80C408151C30583ECBB1C1AAD6C2774DTGDC1dtgruel_"
MIME-Version: 1.0

Select allOpen in new window