Please consider doing a write up on how you resolved this? There must be thousands of people impacted by this.

I've also had this situation when relocating countries. I had to abandon a 15 year old account (for which I also had a valid working recovery email) with a lot of issues recovering online banking etc. (Had to physically travel to another country to restore multiple services associated with the account).

I'm with fastmail now. I will never again depend on a mail service that I am not paying for.