Earlier this morning I tried what I call the qmail-bigdns.patch patch,
available at:
http://www.ckdhr.com/ckd/qmail-103.patch
But, surprisingly, that didn't resolve the problem; I continued
getting the same errors, after qmail-remote spent a fair amount of
time on each delivery attempt.
Just now, after further research, I tried the any-to-cname.patch at:
http://homepages.tesco.net/~J.deBoynePollard/Softwares/qmail/#any-to-cname
It worked like a charm, and qmail-remote takes hardly any time
delivering to earthlink.com now (that is, successful delivery is
taking hardly any time; previously, the failures occurred after what
seemed like several minutes).
Based on the writeup on that web page, and my own experiences, I think
it's safe for me to recommend that second patch for inclusion in most
anyone's qmail setup, and the netqmail people might want to consider
putting it into netqmail-1.06 as well.