Microsoft Authenticator

First of all, I was directed to this website by a Microsoft Support Agent, and I would like to apologize if I am posting in the wrong section.
I am having an issue where I am currently locked out of 2 of my memberships, 365, and GP:Ultimate, due to having changed phones. Yes, the mistake was on my part, I changed my phone without saving a recovery code for the app, but since I have changed my phone number, along with my phone, I am unable to receive a confirmation code to reset anything, or sign in on anything.

Locked out of my XBOX, locked out of XBOX on PC, locked out of Office, not even my account on my computer can be accessed.

The "solution" presented by the Microsoft Support Agent was to simply wait out the 30 days that it takes for the phone number to be changed, as it is supposedly an automated process, that they have absolutely no control over.

What can I do? I am locked out of everything.

Thank you in advance.