How it works: Backup and restore for Microsoft Authenticator

I was having issues with the sound and haptics on my iPhone and needed to do a reset and restore from iCloud. MSAuthenticator was set to back up to the cloud. I had moved all my accounts out of Google Authenticator because of the horror stories I had heard from people losing codes when getting a new phone or restoring. 

Now as it turns out, I ended up losing all the codes I had in MS Authenticator. When going to Recover Accounts, it only loads my account that was associated with the backups in iCloud that I assumed would be used to restore the codes. Ironically, all the codes I had in Authy and Google authenticator are all there without having had to do anything. Is there any way to get them back? Such a bummer.

I have been trying to decide between MS and Authy for a while now and it seems like the choice is now obvious which to go if you don't want to lose all your codes in the event of doing a restore on your phone.