Dear @maarten de bal,
Thank you so much for contacting Microsoft Q&A Support.
I truly apologize that your client is facing with the inconvenience for the Authenticator access when changing to a new phone. In order to help you in this situation, may I know that if he/she uses an alternative verification method: select “I can’t use my Microsoft Authenticator app right now.”? This may allow you to verify your identity via SMS or email, assuming those backup methods were previously set up.
If the above method doesn’t work, since your client's email is a business account (work or school account), and you mentioned that your client is the only Global Administrator and he/she is completely locked out from the tenant. He/she might need to contact us via phone service number: Customer service phone numbers - Microsoft Support. The agent will be able to create a ticket for them under the affected tenant and then transfer this ticket to Data Protection team who could help them to regain access.
Please note that this team is always overwhelmed, so they might need to wait for them to call them, this should take 3-10 working days. I know that this is not a convenient solution to hear but it seems to be the only way, and it's recommended that your client should have a secondary/backup Global Administrator to fix this issue on their own.
Additionally, if your client knows other Global Administrator in their organization, please ask them to follow this article to proceed to reset your client 2FA so that they could re-register again: Manage authentication methods for Microsoft Entra multifactor authentication - Microsoft Entra ID | Microsoft Learn
I hope this information can help your client in this situation.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.