For some reason, since about 3 or 4 weeks ago, my domain (aws.com) receives email from Yahoo, Juno, etc. (qmail users) about 10% of the time. The rest of the emails get kicked back with:
CNAME lookup failed temporarily. (#4.4.3)
I'm not going to try again; this message has been in the queue too long.
Note that I have pretty much narrowed this down to only services that use Qmail.
Our DNS servers and MX records are all good. We've had it verified by 3 third party vendors.
DNS response times average 4 ms and the payload is around 250 or so bytes.
I have opened a ticket with Yahoo, but they seem to have no answer. Juno is blaming my DNS. I blame Qmail.
Any and all advice is welcomed. As you can imagine, this is quite frustrating.