I had this issue on both KloxoMR 6.5 and KloxoMR 7, spereira tip was spot on!
In case anyone is still stumped by this like I was for a long time, here is the solution:
You have to remove the folder /var/qmail/control/tlshosts or rename it to something else and then TLS starts working for all outgoing mail, shouldn't even need to restart Qmail.
Gmail shows that mail is encrypted and CheckTLS Sender test is also successful.
From
http://wiki.qmailtoaster.com/index.php/Tlshosts/exhaustivelist:
man qmail-remote excerpt:
If this file exists no TLS will be tried on hosts other than those for which a file tlshosts/FQDN.pem exists.