Ubuntu 12.04 host lookups extremely slow

Add the dns-search and dns-domain directives to your /etc/network/interfaces file.

Have you got the ipv6 kernel module loaded?

If you have, your system will search for an AAAA record first, and if that returns a record, it'll preferentially use that over the A record, and the problem is that the service that requested the lookup will try and connect using the AAAA answer, which might not be supported for the IP stack you're using.

Disable the ipv6 kernel module, and this problem goes away.

Might not be that, though. You could always install dnsmasq locally so that your nameservers in /etc/resolv.conf is set to lookup against localhost, and dnsmasq will look up to the upstream nameservers, and cache the result, so the first one will be slow, but all subsequent ones will be lightning fast.