They could be purchasing DNS query logs from ISPs.

Serious question: Do you really think that Cloudflare is trying to keep these kinds of thing private? If so, I'd suggest that's not a reasonable expectation.

Related question (not rhetorical). If you do DNS for subdomains yourself (and just use Cloudflare to point dns.example.com at your box) will the subdomain queries leak and show up in aggregate datasets? What I'm asking is if query recursion is always handled locally or if any of the reasonably common software stacks resolve it remotely.

As well as assuming Cloudflare sells DNS lists, it's probably safe to assume the operators of public resolvers like 8.8.8.8, 9.9.9.9 and 1.1.1.1 (that is Google, Quad9 and Cloudflare again) are looking at their logs and either selling them or using them internally.

If you just use Cloudflare as a registrar, then they can't see what resolution happens on your servers.

If you delegate a subdomain through Cloudflare to your own DNS servers, from what I remember from the animal book, the recursive server should ask Cloudflare for the address of the machine to which the delegation has been made (yours), and while any further resolutions would be answered by your machine, Cloudflare would at very least know of every query to that subdomain.

If you delegate a subdomain and have subdomains under that subdomain, then Cloudflare would only see resolutions to that subdomain and not to the sub-subdomains.

In other words, for most things, they'd have full insight.

maybe your server responded to a plain ip addressed request with the real name...

Host header is a request header, not a response one, isn't it?

He said he used a wildcard cert though. So what part of the response would contain the subdomain in that case?