I would think a cert shouldn't be issued with an expiration date after that of the domain registration itself.

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.