The only thing that I could see working is to 'establish a tree of trust' going from 'trunk'
root dns servers to 'branches' to the 'leaves'.
Each DNS server would have to register with the ones it communicates with and uses something
like TLS or PGP signing to communicate with one another so that the identify of the sender is
confirmed by the signature data contained in a packet (once you get a signature then you
wouldn't have to sign each packet, just as long as the data can be compiled and have it's
final checksum confirmed then that's fine). Then when a person requests a DNS address the
message will have to transverse up the tree to the nearest DNS system (or 'common link') in
the chain of trust and then back down (this would probably require a separate routing
protocol, or tying into existing protocols, for finding these paths).
The DNS server would have to establish it's identity with it's neighbors when it's first
brought up, and that's were the next window of vulnerability will be.
That's a lot of overhead, though.