Many thanks @eskimo for the very insightful and honest answer. In the latest 30 days the issue affected ~0.05% of our users, it's a fraction of the whole population, but still a significant number. We will try to add some workaround to help users to re-generate and re-enroll the key if we see this issue happening, currently it's treated as a transient error so users can retry, but as you mentioned, it will never work again.
Do you have enough data i.e. sysdiagnose reports to debug it? I can help to get more reports. We get info about this issue almost in real time and have infrastructure/processes in place to follow up with users and collect diagnostics (including sysdiagnose) if needed.