I lost a Yubikey, so I revoked the subkeys on it. Github didn't let me update the existing pubkey, so I had to remove and re-enter it. Now all things signed by the revoked key, despite being before the revoke date, come up as unverified.

I'm not sure if it's a me issue or a PGP issue or a GitHub issue, but it's a pretty broken system.