This happened to me but because I broke my phone. My broken phone had Google Authenticator on it and I don't have my backup codes since I've had authenticator for years and never thought to redownload them. Anyways, now I can't login to my Facebook or Twitter anymore. Facebook doesn't seem to have any kind of account recovery and the methods they say I can use (e.g. log in from another device and you'll get a notification) don't work. I even have my phone number logged with them but apparently not as part of 2 factor, so I can't recover my account that way either.
TBH this experience has really made me question using an authenticator app every again.