Same issue with me
Apr 12 08:29:19 server send: delivery 1: deferral: CNAME_lookup_failed_temporarily._(#4.4.3)/
I think I have a clue but I'm not sure, I read somewhere that qmail can only handle DNS lookups (including cname and mx) up to a certain amount of bits and to be able to work with bigger lookups it need to be patched, but since qmail is installed from the kloxo repos I haven't done any patching and to be honest, I'm not even sure if I know how to do it.
I check the records for the domain that I want to send an e-mail and they are fine, also that error is just happening for a few of the e-mails I try to send from my server