I'm currently locked out of a Gmail account I have the password for but Google decided that isn't enough; it doesn't like my IP address and wants me to verify against a phone number I no longer have.
I had the same. There's a good chance someone else has that number now - add them on WhatsApp/Facebook Messenger/etc by phone number, Google their number and try to find them, or call them.
In my case, I was able to recover the account by communicating with the new owner, and him quickly sending me the 2FA code he got from Google when I tried to log in.
6 months. That's all it takes between the last time a user successfully used a phone number, and a new user getting assigned the same number with prepaid SIMs in Germany.
6 months is a damn short time.
Or maybe they should stop being idiots and allow people with strong passwords to... just use passwords to authenticate.
Maybe some type of "I know what I am doing, kindly fuck off Google" option.
Tbf if you really knew what you're doing, you wouldn't be using gmail.