Rerverse dns lookups on Windows block for several

I'm using Java's InetAddress.getHostName() to perform some reverse DNS lookups, and something seems wrong with the time it takes. Here's a code snippet:

public static void main(String[] args) throws IOException {

byte[][] addresses = new byte[][] { { 10, (byte) 0, (byte) 0, (byte) 138 }
    , new byte[] { (byte) 216, (byte) 239, (byte) 49, (byte) 245 }
    ,{ 8, (byte) 8, (byte) 8, (byte) 8 } };

    for (byte[] addr : addresses) {
        InetAddress inet = InetAddress.getByAddress(addr);
        long before = System.currentTimeMillis();
        String hostName = inet.getHostName();
        System.out.printf("%20s %40s %5d\n", inet.getHostAddress(), hostName, (System.currentTimeMillis() - before));
    }
}

And here's the output on my machine:

    10.0.0.138                               10.0.0.138  4503
216.239.49.245                           216.239.49.245  4591
       8.8.8.8           google-public-dns-a.google.com     8

Resolving both 10.0.0.138 and 216.239.49.245 takes 4.5 seconds each, regardless of the number of times I've ran this code. This seems to happen with all unresolvable IP addresses.

This isn't a networking issue since according to a wireshark capture, DNS queries aren't even sent when this code is run unless the DNS cache is cleared first (and then the results are even slower - around 4.7 seconds per resolution).

So does it actually take Java 4.5 seconds to timeout against the OS's local DNS cache? That makes no sense. The command line utility nslookup returns (unresolvable) results for these IP addresses much faster, and it doesn't even use the cache!

Can some one explain this behavior and suggest way to speed up these resolutions? The only thing I can think of without turning to external libraries is using multiple threads so at least the 4.5 second timeout will be executed in parallel.

For reference, I'm using JDK 7u71 on Windows 7 x64

Edit1: This question seems relevant, but the answer there says that the performance depends on the network, which is not what I observed.

Edit2:

This seems to be a windows issue. A machine in the same LAN, that uses the exact same DNS, running OpenSuse 13.1 with JDK 1.7u67 returned the following results:

Without DNS caching:

10.0.0.138                                   10.0.0.138  116             
216.239.49.245                           216.239.49.245  5098             
8.8.8.8                  google-public-dns-a.google.com  301

With DNS caching:

10.0.0.138                                   10.0.0.138  5
216.239.49.245                           216.239.49.245  9             
8.8.8.8                  google-public-dns-a.google.com  40

Edit3:

Eventually I had to work around the issue by doing my own reverse DNS lookups using dnsjava.

It looks like an issue with the implementation of the DNS client in Windows. I just tried the same logic in C#.NET:

 static void Main(string[] args)
    {
        byte[][] addresses = new byte[][] { new byte[] { 10, (byte) 0, (byte) 0, (byte) 138 },
            new byte[] { (byte) 216, (byte) 239, (byte) 49, (byte) 245 },
            new byte []{ 8, (byte) 8, (byte) 8, (byte) 8 } };
        foreach (byte[] addr in addresses)
        {
            IPAddress inet = new IPAddress(addr);
            DateTime before = DateTime.Now;
            String hostName = null;
            try
            {
                hostName = System.Net.Dns.GetHostByAddress(inet).HostName;
            }
            catch { }
            finally
            {
                DateTime after = DateTime.Now;
                Console.WriteLine("{0} {1} {2}", inet.ToString(), hostName!=null?hostName:"N/A", after.Subtract(before));
            }
        }
        Console.ReadLine();
    }

these are results:

   10.0.0.138 N/A 00:00:04.5604560
   216.239.49.245 N/A 00:00:04.7984798
   8.8.8.8 google-public-dns-a.google.com 00:00:00.0060006

The interesting part is that after a DNS cache flush, Windows sends all DNS requests to the network. The DNS server replies after 0.25 second but if the answer is "No Such Name", the DNS client still blocks for the entire duration of the timeout.