Couldn't you blacklist all subdomains of the 1st party and whitelist the few that are actually real?
Or, assuming they have a small list of subdomains that redirect to ad servers, you could generate a list with a script that checks all their subdomains and creates a block list based on that. For example, the site discussed in the OP has all their subdomains listed here: https://crt.sh/?q=%25.liberation.fr
Edit: looking at the OP case, it seems like they only have one ad domain. I'm not sure I see this as a serious issue until multiple sites start rolling out thousands of subdomains, some pointing to back to the real server, others pointing to the ad server. Maybe that will happen but it's a pretty big barrier to entry, and just short of proxying everything through the 1st party.