Here is the /etc/resolv.conf file from that VPS, generated by dhclient:
domain members.linode.com search members.linode.com nameserver 109.74.194.20 nameserver 109.74.192.20 nameserver 109.74.193.20
It looks like the 109.74.194.20 server is overloaded and returns a SERVFAIL ("server failure - The name server was unable to process this query due to a problem with the name server") answer from time to time. Unfortunately, Debian has a bug in its version of libc that prevents the resolver from trying the other (working) servers if the first one returns an answer indicating a temporary failure.
The bug does not exist in glibc-2.12.1 on my Gentoo box at home. However, if the server does not respond at all, the Gentoo resolver spends 15 seconds before trying the next one, which is also not nice.
To work around the bug, you can run your own DNS server on 127.0.0.1 that forwards all queries to the official servers, and put 127.0.0.1 as the only nameserver in /etc/resolv.conf.
