Authenticator bug

Question

I got a new phone and thought my accounts would simply transfer to my new phone via the authenticator app backup, which is not the case. I lost all of my accounts that had two factor authentication, and now I cannot access most of them. Is there a way to regain access to these accounts? I do not have backup codes or anything but I do have access to my Microsoft account if that helps. Please let me know what can be done, if anything, because some of these accounts do not give me ANY other option to gain access to the account if I do not get authenticator codes or the backup codes that were associated with the account.