This is getting more and more annoying as sites switching to DNSSEC are likely to produce DNS replies >512 byte.
A blog post describing the issue and workarounds is available at https://www.webfactory.de/blog/patch-qmail-in-ubuntu-to-avoid-cname-lookup- failed-temporarily-errors. Two patches (to double-fix this) are attached, at least one of both is supposedly endorsed by DJB himself: http://marc.info/?l=qmail&m=128699053800323&w=2
0005-remove-cname-check.diff
Description: 0005-remove-cname-check.diff
0004-oversize-dns.diff
Description: 0004-oversize-dns.diff