A third party server sends us signed messages that we verify. When its certificate is about to expire, the third party generates a new key pair and sends us the new certificate.
At some point, the server will start signing with its new key, requiring that we use the corresponding new certificate to verify.
How can we make this two-side replacement process accurate and easy? It would be a hassle if any messages were rejected due to timing issues (i.e. party A switches, then a message is sent, then party B switches).
An obvious solution might be to try all non-expired keys, but that seems like code pollution. Particularly because we only face this challenge in some scenarios, meaning some occurences of signature verification have to bother with multiple certificates, while others do not.
Another idea is to specify a timestamp. However, server clocks might not be in sync, and memory caches (e.g. with a 15-minute expiration) would interfere even more.