Just installed a basic Debian 6 server and was amazed about how much time it took to resolve any domain name; at least 4 seconds. But I found the solution: if you don’t use IPv6 then disable it.
Check the IPv6 alias:
grep ipv6 /etc/modprobe.d/aliases
This should give you this entry:
# alias net-pf-10 ipv6
Edit that file and change the line to:
alias net-pf-10 off ipv6
Then reboot. As always, YMMV.