Ondrej,
I may have missed parts of the previous discussion, but why are you not encapsulating the whole DNS request from the client? Various flags and other options (e.g. EDNS0) would be quite useful to be able to transport across the TOR network.
jakob