> please point me at the technology that lets you tell which key a message is signed with given only the signature and the verification key?
In this scheme you already know which key the message should have been signed with, so you only need to check that one key. However, if all else fails you could generate every signing key from the verification key up to the present and calculate the message hash for each key, checking it against the provided signature.
> Even if you can do this, you still have the question of how do you know that message should have been signed by key 20 instead of key 2000, or better still, how it should have been signed by key 934503459 instead of 934505459.
I already answered this at least twice. The initial time t0 and key change interval are known. The message includes a timestamp t[m]. If it was really logged at that time, the signing key will be K[floor((t[m]-t0)/interval)].
Since the question has come up, the logging system knows t0 and n in addition to K[n], and rotates keys however many times are necessary after downtime until n is correct for the timestamp of the next log entry.