<a href="http://freshmeat.net/projects/nstx/">NSTX</a>

うわあ。実装が存在するんですか! < IP over DNS

NSTX (the Nameserver Transfer Protocol) makes it possible to create IP tunnels using DNS queries and replies for IP packet encapsulation where IP traffic other than DNS isn't possible.

Slashdotでも、ずいぶん昔にとりあげられていたようです。