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.