And the ultimate answer came from Friedemann Stoyan via the debian-ipv6 mailinglist: It's a know debian bug: libc6: Resolver prefers IPv4 to IPv6 in some cases. The bit where RFC1918 addresses trigger this bug is especially evil: in my opinion users with ipv4+nat (rfc1918) and ipv6 (globally routed) on their network would be better suited with a preference for ipv6.