Don't forget Google's free hosting of Javascript libraries and webfonts. The cost of serving those is recouped by dropping a cookie on you. Also Google DNS can give them great insight into domain popularity.
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.
That may be, but it seems that Akamai CDN is still giving them a data feed. From that press release:
"As a result of the pixel-free technology partnership, MediaMath's clients will gain access to more data for audience segmentation, retargeting, and optimization, with quick and easy activation."
