That would work with common gTLDs, but some ccTLDs have a very annoying policy where they only allow one-year renewals and the renewal doesn't show up in the wh

That would work with common gTLDs, but some ccTLDs have a very annoying policy where they only allow one-year renewals and the renewal doesn't show up in the whois until the last moment. Anyway, it's trivial to find out whether a domain was expired and re-registered. The date of initial registration in the whois will change, so you can just compare it with the value you saw when you first issued a certificate for that domain.