This one has me stumped. We've started experiencing problems sending email to certain domains. I'm seeing messages such as these in our mail logs:
Domain of sender address <us@here> does not exist (in reply to MAIL FROM command))
Domain of sender address us@here does not resolve (in reply to MAIL FROM command))
Some of the big domains that we're having problems with are rcn.com, att.net, and pwc.com. Many other sites have no problems, though.
From what I've learned, this happens when the destination mail host cannot find an A record for our domain; but our domain certainly does have an A record (and MX, SOA and NS records). We're running three Bind 9.2.4 servers on Redhat machines, which appear with a whois.
Watching the queries.log, I see a lot of queries coming in from external hosts. I'm also able to perform digs against our name servers from off site hosts. I've also used some online DNS test sites, such as intodns and a few others, and none report any major problems for our domain.
I'm stumped at this point. Has anyone experienced this or have any suggestions?