Turns out Microsoft authenticator backup function is not perfect. Despite it says it have backed up to the cloud, I cannot recover the backup, it's saying that there's no backup.
So, PSA: restore Microsoft authenticator to a backup phone first.
Thus making sure that the backup is indeed there, and you have a working backup authenticator.
Don't be like me and stuck in the nightmare of lost 2fa and hunting backup codes. Although to be fair, it was probably caused by an obscure bug that I triggered simply because I'm magnetic to bugs
So, PSA: restore Microsoft authenticator to a backup phone first.
Thus making sure that the backup is indeed there, and you have a working backup authenticator.
Don't be like me and stuck in the nightmare of lost 2fa and hunting backup codes. Although to be fair, it was probably caused by an obscure bug that I triggered simply because I'm magnetic to bugs