Interesting. Was your 2FA setup to use Google Authenticator or regular SMS? It's been a while since I used Google services but from what I recall from a previous company where we used Gmail was that the only way to do 2FA with Google Authenticator if you lost access to the phone was with a backup code you are given at 2FA setup time. Is that no longer the case?