[mindslight]

This isn't a concrete software recommendation, but the DNS would lend itself exceptionally well to a distributed p2p resolver that would prevent most queries from hitting centralized servers in the first place - it's just a simple distributed database. You'd need some sort of multiparty trust metric to avoid tampering (or DNSSEC), but modulo that peers could just freely pass around records.

There would be a little more complexity these days with large companies changing answers based on the address of the requester, but that doesn't seem too hard to account for or even just ignore. And to reduce traffic even further, you could take some liberties with TTLs, for records that actually don't change often.