If rotation is the secret sauce, then the best strategy is to rotate after every use. In which case, why not just build that into the system:

1. Client holds key.

2. Client exchanges key with central agency for token. Token expires after a short time period, making long-term storage and leaks useless.

3. Client gives token to company.

4. Company validates token with central agency.

And now we've reinvented OpenID. And SecurID is nothing but a piece of hardware that can perform (2) in a decentralized manner. We could maybe modify (4) to potentially be more useful for this specific use-case:

4. Company exchanges client identity token with central agency for a validation token that can be stored long-term. Validation token signifies that an identity token was received and exchanged, for legal purposes.

What I don't know is how to protect this validation token from becoming valuable beyond the above use-case. If it's proof of something, then it becomes valuable for that proof... So it would would have to be scope-limited in ways that make it useless for proving anything other than that exact exchange. Off the top of my head, obvious scope limitations are: client, company, and timestamp.