Note: Since you are using English, although the site locale is de-de, I will response to this question in English. If there is anything unclear about my reply, please leave a comment and I will get back to you as soon as possible.
Dear Justin Wappelhorst,
Based on your description, since you are the only Global Administrator and have lost access to all registered MFA methods after changing phones, this is considered a tenant admin lockout scenario. In this situation, neither forum moderators nor community users can directly reset MFA or modify authentication methods for your account.
I understand you've already attempted the available recovery options, including contacting support by phone and trying to create a separate tenant to open a support request.
While I cannot guarantee the outcome, I have seen cases where calling back and going through the IVR flow again eventually connects customers with a support representative. I am not sure which options were selected during your earlier calls, but if you decide to try again, you may wish to follow prompts similar Customer service phone numbers - Microsoft Support
To help you navigate the automated phone system (IVR), here's an example of what the conversation might look like:
IVR: What kind of problem are you worried about?
You: Admin account locked
IVR: What kind of product do you use?
You: Office 365 for business
IVR: Does it count for education or business?
You: For Business
IVR: Are you an admin?
You: Yes
IVR: Do you have another administrator in your organization?
You: No
IVR: Need a service request?
You: Yes
This should help you connect with a live support agent who can help you directly.
Since this involves a sole Global Administrator account with no available MFA methods, Microsoft Support remains the only team that can review the ownership verification process and determine the available recovery options.
I genuinely hope you are able to reach an agent and get the case moving forward as soon as possible.
Note: Please follow the steps in the forum documentation to enable e-mail notifications if you want to receive the related email notification for this thread.