One highly unlikely, but occasionally possible, cause for this error is if having added the same key twice with different expiry dates. You would likely know having done so for this answer to be relevant to you.
This can happen, as it did for me, when hosting your own repository with your own keys. If you, when the key is about to expire, simply extend its lifetime rather than change it, and if you installed the original key using preseeding but the updated key using a deb package, then the old key will be in
/etc/apt/trusted.gpg, while the new one ends up as a separate file under
/etc/apt/trusted.gpg.d/. The old key will shadow the new one, which will be completely ignored by
apt-key. Remove the old key by running
gpg --keyring /etc/apt/trusted.gpg --delete-keys <keyid>, and your new key will become detected.
This is a bit of a non-standard corner configuration, but I hope my answer can save some confusion in case anyone else encounters this issue due to the same reason as I did.