Thank you for reaching us!
I understand that you would like to remove the existing MFA and re-register again with the new Phone.
If you have access to your account, you can add the Sign-in method from the below link.
https://mysignins.microsoft.com/security-info add the new MFA and the remove the previous MFA.
If you are unable to access the above MFA needs to be reset and set it up again, for this, you’ll need assistance from an administrator within your Entra ID tenant.
If you have one account with admin role and if you are blocked entirely, you can reach out to our support team. You can look into below article to get support numbers depending on your country.
or creating a ticket through a different account: https://learn.microsoft.com/en-us/microsoft-365/admin/get-help-support?view=o365-worldwide#phone-support
Create a ticket with Microsoft support team. Give them the tenant ID which is locked out in your description. Tell them that no admin account has access anymore and your partners also have no access anymore.
Once you create a ticket with support team you will have to work with our data protection team. You will have to first prove your identity against your tenant for security purpose. Post that this team will help you with help you in getting access to your tenant or unlock your account depending on your scenario.
Read More: Manage user authentication methods for Azure AD Multi-Factor Authentication
Hope this helps. Do let us know if you any further queries by responding in the comments section.
Thanks,
Akhilesh.
If this answers your query, do click Accept Answer
and Yes
for was this answer helpful. And, if you have any further query do let us know.