My understanding is that, because of the additive nature of the ledger, outdated DDOs - hence, outdated pub keys - will never be overwritten, so a mechanism could be devised for the verifier to get the old keys together with the most recent one.
However, I concur it is unpractical to check the claim signature against 100 old keys. One option could be to include the reference to the correct version of the DDO into the signature (via a signed attribute).
This approach resembles a common practice in digital signature, where the X509 certificate is embedded into the signature. The certificate (i.e., a signed binding between a key and an entity) would be replaced in this case by the proper DID-DDO association in the ledger.