So, I have finally nailed it. It seems that my last post regarding this topic was only a partial solution and in some cases didn’t solve the problem of IPv6 DNS requests at all. It seems that for example OpenSSH is compiled to try AAAA record before A as default in many distributions. The problem is that GLibC resolver is sending A and AAAA DNS request at once. And even if it gets reply to A it still waits until timeout for AAAA if you don’t have any IPv6 routers present on the network you’re connected to.
The solution is simple. Newer versions of GLibC (2.10 and later) resolver has option to try one request at a time. Edit your options in /etc/resolv.conf (or if you’re using resolvconf probably with DHCP client edit /etc/resolvconf/resolv.conf.d/tail) and add a line like this:
options single-request
And that’s all. You’re done. (In case of using resolvconf you should reload it with /etc/init.d/resolvconf reload).