Hi Dilan,
Thank you for reaching out and sharing your experience. I understand how frustrating it must be to switch to a new phone and suddenly lose access to your accounts especially after spending hours trying to get help without success.
The reason you're receiving codes for only one account is likely because that account was backed up to the cloud and successfully restored while the others were not. Microsoft Authenticator relies on either iCloud (for iPhones) or cloud backup via a Microsoft account (for Android) to transfer account data. If backup wasn’t enabled on your old phone or if the accounts were added manually without backup they won’t appear on the new device automatically.
To resolve this you can try the following steps
For personal Microsoft accounts, go to account recovery and use an alternate method like a recovery email, phone number or saved recovery code to verify your identity. Once you're back in, you can disable two-step verification temporarily and reconfigure the Authenticator app on your new phone.
For work or school accounts, if applicable, you’ll need to re-register the Authenticator app by signing in at aka.ms/mysecurityinfo. If you don’t have access to backup methods, Microsoft offers a recovery form to help verify ownership.
If you saved backup codes during your initial setup those can be used to log in and reset your Authenticator settings.
May I ask if you still have access to any recovery methods like a backup email or phone number linked to those accounts? Also if you’re using a personal Microsoft account I can guide you through the recovery form process to regain access.
I hope this answer is helpful if you have further questions feel free to reply back
Regards,
Marcelo