(In theory, a site might generate new subdomains and DNS responses for them on the fly, making this approach unworkable. In practice however, most sites have moved entirely to HTTPS, which means that unless you give your ad host a certificate for *.yourdomain.com, all the subdomains have to be known in advance and show up in certificate transparency logs, making them easy to block.)
Not really, other than as you say simply going elsewhere. The trouble is most users don't know to go elsewhere as they don't know about the matter without digging.
You could start treating changes of sub-domain the same way cross-domain references are handled by tools that block 3rd party cookies, but there are plenty of sites that use multiple sub-domains which have genuine uses for shared cookies (single sign-on for instance) that might be broken by this so you'll have an initial inconvenience of white-listing them. Also if a previously white-listed site goes rouge, detecting that could be difficult, or at least fraught with false positives.
Tor exit IPs trigger lots of CAPTCHAs and other abusive behavior. But if it's just that you want to prevent tracking, it's enough to run a VM that connects through a VPN service. Or a nested chain of them.
I mean, whoever can track the whatever about Mirimir, and I couldn't care less. Or any of the other personas that I use.
It is also worth noting that caches other than the browser cache can also be abused to track users: http://dnscookie.com/
[1]: https://medium.com/@stoically/enhance-your-privacy-in-firefo...