IP based tracking still works most of the time. Dynamic IPs change very infrequently, and NAT combines IPs in physically (and often socially) close groups. It isn't perfect, but a lot of those requests can probably be mapped back to those cookies.

Google's entire business is based on building large database of tracking (and other) information; obviously their DNS is just another data source.

Just skip the recursive resolvers and run a local caching DNS server that starts from the root zones.