Please help! This exact thing happened to me tonight and half of the apps missing are ones I use for work and networking!!!
When I turned on my authenticator app today, for some reason, I was signed out (I'm normally signed in), so I had to sign back in on my account and, as soon as I did, nothing was listed under my authenticator accounts, only "Start Recovery" or "sign in"
I tried starting recovery, but received the EXACT same message as the original poster did, "There is no backup stored in your account, use a different personal account"
So next, I simply tried to "sign in", and now the only thing that appears under my Authenticators is Microsoft itself... not Discord, not Steam, or half the other things I use the authenticator for.
Now I can't sign in on my vital business applications because the apps that were there before are just simply gone now!