Sounds like a DNS problem (OK - I'm picking on the easiest one to solve
) Can you try a 'dig' for any of the domains you're trying to send to?
Also - if you want less cryptic output from qmail's logfile, try piping it through the (usually installed) tai64nlocal
Code:
tail -20 /var/log/qmail/current | tai64nlocal