You could use k-Anonymity to request a handful of results, without the dns server knowing which result you were looking for. hash the hostname, return all results that have the same x letters as the beginning of the hash. at no point, would the actual site you are requesting leave your lan. your dns resolver would know within 1/400th (how every many results it replies with) which site you were asking for. After time, and recording patterns, they might be able to make educated guesses of which site you were requesting, but it would not be concrete evidence.
k-Anonymity doesn't really work with non-uniform distributions. E.g. if x is your hash prefix and d is a particular domain that matches that prefix, then we can apply Bayes rule:
P(d|x) = P(x|d) * P(d) / P(x)
P(x|d) is 1 in this case (the hash is deterministic), so the probability is just P(d)/P(x). E.g. if "facebook.com" doesn't have a hash collision with another similarly popular site, then you can be pretty sure that a request for hash("facebook.com") is a request for "facebook.com" for a high proportion of requests.
This also adds some overhead. E.g. 400 IPs+TTLs probably wouldn't fit in a 1500 MTU packet, so it might have to be split up or k reduced to fit.
From the ISP perspective, they can also tell which of the k you were interested in because you will probably send a SYN packet to that IP address. Unless you also send 400 SYN packets...
https://blog.cloudflare.com/validating-leaked-passwords-with...