It is worth noting that DNS lookups can be done via Tor. In effect that gives you 1000+ proxies instead of 56 or 4. BitcoinJ already has code that can do this.

I would agree that it makes sense for proxying of DNS requests to be an optional part of the protocol. Wallet developers can then compete on privacy vs robustness vs whatever other issues there may be.