Question : Issue with DNS

hi Experts ,
we received couple of calls from couple of domains that when they are trying to send us an email they get the message (bounces back )
We are using exchange server 2003 SP2
[email protected]   Name server: lockelord.com :host name lookup failure

etc,,,,

any ideas ?  Nobody else has called with this issue.  
I checked at the mxtools and when i did an MX lookup for lockelord i got an error.
How can i fix this issue ?

Any ideas would be appreciated.

Answer : Issue with DNS

i believe there is some error with that domain, so far you don't have any problem with other domain's, i have checked the domain just now and i found the domain is active .
when did you try last time??

Also try this site to check the domain

http://www.dnstools.com/

also this link seems useful

http://www.chicagotech.net/dnstroubleshooting.htm