Linux – Reverse DNS lookup takes 5 seconds to give up

I have a Debian 2.6.26-2-xen-amd64 system which takes 5 seconds between the second and third failed reverse DNS lookup. All (most?) other similar systems here do the three lookups with little wait between them.

I have tried to figure out what might be causing the difference, but, so far, I have been unable to do so. What might it be?

EDIT

Though I have observed the problem when logging to the machine with sshd, knowing slowness there is usually a problem with reverse dns, I have tested it using host. This is being provided by the package host, version 20000331-9.

Here's the tcpdump output of the test on two machines.

Host with delay:

11:47:58.883885 IP 192.168.20.127.48797 > 172.16.1.1.53: 13275+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:47:58.884258 IP 172.16.1.1.53 > 192.168.20.127.48797: 13275 ServFail 0/0/0 (42)
11:47:58.884326 IP 192.168.20.127.34876 > 172.16.1.1.53: 13275+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:47:58.884804 IP 172.16.1.1.53 > 192.168.20.127.34876: 13275 ServFail 0/0/0 (42)
11:48:03.892639 IP 192.168.20.127.43032 > 172.16.1.1.53: 21337+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:48:03.893282 IP 172.16.1.1.53 > 192.168.20.127.43032: 21337 ServFail 0/0/0 (42)

Host without delay:

11:15:58.222147 IP 192.168.21.26.50046 > 172.16.1.1.53: 2040+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:15:58.222611 IP 172.16.1.1.53 > 192.168.21.26.50046: 2040 ServFail 0/0/0 (42)
11:15:58.222718 IP 192.168.21.26.51288 > 172.16.1.1.53: 2040+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:15:58.223102 IP 172.16.1.1.53 > 192.168.21.26.51288: 2040 ServFail 0/0/0 (42)
11:15:58.223197 IP 192.168.21.26.36545 > 172.16.1.1.53: 20425+ PTR? 30.4.16.172.in-addr.arpa. (42)
11:15:58.223550 IP 172.16.1.1.53 > 192.168.21.26.36545: 20425 ServFail 0/0/0 (42)