How to log into Authenticator when the account *needs* Authenticator to authenticate the login?

Question

Authenticator gave me a weird error message asking me to sign in again yesterday. Up until that time I've been using it perfectly well on my phone. I add my Microsoft account email address (which I have previously removed the password from to allow Authenticator to handle) and, of course, it gave me a random 2-digit number to type into Authenticator, receive an authenticated number and proceed with the log in. But since I was trying to sign into Authenticator at the time I couldn't do that.

Everything is backed up, so I cleared the local data and set it up again: Start recovery from backup, enter the MS account email, tell it that I don't have access to Authenticator and receive the verification code via another email address. It then wants to do this again because I have 2FA turned on (weird how it offers to send it to the same 'alternative' email address as I've just used, but there you go). When I enter the address it tells me I've requested too many codes today and I have to wait 24 hours. OK, so I try the alternative verification method of receiving an SMS on my phone: "Sorry, this service is unavailable". So now what? I need Authenticator and I cannot log in because I also need Authenticator to do that, it seems!

Anybody got any bright ideas about how I can get out of this bind?

Thanks,

Angus