Comment 63 for bug 94940

My network was showing this (multiple) 5-second timeout problem. To test it, I turned off DNS caching
# /etc/init.d/nscd stop
and then
# time curl -I www.google.co.uk
which consistently took more than 5 seconds.
I tried several of the approaches described above, and eventually determined that the problem was primarily down to the modem/router that I was using; its internal DNS could not handle two concurrent UDP DNS enquiries. In addition, if I sent out the two UDP DNS queries (A and AAA) in parallel to an *external* DNS server, the router often dropped one of the incoming reply packets, presumably because its stateful firewall only recorded sending a packet, not how many had been sent, and so cleared the entry for the DNS server when the first reply arrived.
In the end I settled on this in /etc/nsswitch.conf:

hosts: files nis mdns4_minimal dns [NOTFOUND=return] mdns4

(I use NIS, but not mdns - but I've left it in there in case a friend brings a machine that uses it).
But more importantly, I put this in /etc/resolv.conf:

options single-request
nameserver 213.120.234.2
nameserver 192.168.1.1

where 213.120.234.2 is one of my ISP's public DNS servers, and 192.168.1.1 is my own router as a fallback. With this configuration, the curl command above completes in well under one second. So in this case at least, the problem is not mdns but the limited capabilities of the ADSL router. I think I'll switch over to running a proper DNS (and DHCP) service on one of my own machines now, rather than relying on the router!