I don't think what you are seeing is normal and to me it's all hinting at something local. I feel that there is something common to all your setups causing this. I don't think it's the upstream DNS providers.
One thing that pops to mind is UDP packet fragmentation. Perhaps there is something in the network setup or filtering (iptables) which is causing UDP packets to fragment but is dropping the second part of the fragment? This is a surprisingly common problem on a lot of firewalls, for example Sonicwall. Perhaps force dig to use TCP to see if the results are different (dig +tcp <host>).
That's just one possibility among many. Swap out one of the machines for a totally different system (Windows laptop maybe?) and repeat the tests. If you don't get the same failure rate while on the same connection, then you know it's your setup.