I use subdomains and a wildcard cert to partly obfuscate this.

I do the same, but I switched from cert-per-subdomain a couple of years ago.

They're either using Passive DNS logs or a historical dataset.

When I stood up some sites last year, I used codenames for the subdomains thinking I was obfuscating a little. I didn't know about the transparency logs until months later.

TIL about Certificate Transparency (they didn't teach that in security school)