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.

But you can't serve the same ads to the teenager of the family, Grandma and Dad...

And the IP may be a public network.