Just put the recursive resolver directly onto the phones?
Also increases "snappyness" of web browsing by a lot as it cuts down the latency for dns queries to <1ms (with aggressive caching + serving expired records + automatic revalidation of cached entries, and so on, the typical DNS server optimisations).