I've been through the process of recovering an old account and I can share some tips, feel free to email me if you'd like (address in my profile)
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.