“communications failure”

Exchange 5.5 SP 3. Windows NT SP 4.

Trying to send e-mail to two different domains. flash.net and texas.net. When anyone in our office tries to send to these addresses they get a NDR:
“Unable to deliver the message due to a communications failure” We can send to any other domains. We have looked in Exchange Admin and there are no message filters. We have also looked in DNS Admin and cleared the cache. If I use my personal e-mail through my ISP I can send e-mail to flash.net and texas.net. We even opened the firewall to let all traffic through to and from our Exchange server. Any ideas?