Random users getting Invalid Code error when trying to register for self service

Random users getting Invalid Code error when trying to register for self service

We have had random users, using both iPhones and Androids, get the Invalid Code when either scanning and manually entering the code from the Self Service page.
The time and date have been verified on both the computer and the mobile device. 



In some instances we found that by removing the AD Self Service mobile app, then removing the authenticator, reinstalling the authenticator, that could get registered. Then they could reinstall the AD Self Service mobile app.

These users are having issues with both the Microsoft Authenticator and the Google Authenticator. The latest is on Android 11, Galaxy S20.

How do we resolve this issue.