I had just the opposite problem - I've had the same phone number linked forever, but I left my backup email set to my work address at a previous job. I wasn't able to reset my password without access to the latter.

After about 5 years of occasionally flunking the questionnaire to prove I was me, Google relented and allowed me to update my password via a code sent to my phone and another sent to the gmail account itself.

Which is to say that I was saved by a device that had access to my original gmail for five years without ever asking for the password. Which doesn't seem like an example of sterling security.