Exchange 5.5 Host Resolution error

I have been running an exhcange 5.5 server for many years and just recently we have had an issue with a certain client. Our mail system works fine until we try to email a certian domain. This domain can email us just fine, but when we try to email them we get the followning Non delivery error:

network error during host resolution.

I can telnet into them and send with no error, so I have to believe that the problem is on our side. I do not have them filtered so that is not the issue. Here are the reqs:

Exchange 5.5
Sonicwall Firewall
We host our own dns

I am lost at this point and do not know where to look next. Any help woud be great. And if you help me resolve you WILL get the points!!!!

THANKS,

Stephen(My Brain Hurts At This Point)Turner
sturner@mustangtampa.com