Are you using free DNS servers, like 4.2.2.2 or 8.8.8.8 instead of your ISP's servers? From what I have found out when facing this very same problem last year, these free services by Google and ATT block SMTP resolution requests because they are overwhelmed by too many. I switched to the ISP's DNS and the problem evaporated.