@Adam tom
Thank you for your detailed post! Have you looked into the troubleshooting steps for backup and recovery problems along with the MS Authenticator FAQ documentation? If you have access to your AzureAD tenant within the Azure Portal, you can try setting up the Authenticator App again.
Azure Portal -> Azure Active Directory -> User -> Select your desired user -> Authentication methods -> Select "Require re-register MFA"
Navigate to aka.ms/mfasetup -> Select "Next" and sign-in to go through the entire set up process again
If you don't have access to the Azure Portal, you can always run the Set-MsolUser StrongAuthenticationMethods command to re-require MFA:
Set-MsolUser -UserPrincipalName admin_mydomain.com#EXT#@mydomain.onmicrosoft.com -StrongAuthenticationMethods @()
If you have any other questions, please let me know.
Thank you for your time and patience throughout this issue.
----------
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.