> I will never use their services again, I was really digusted by this failure
Isn’t this inherent to not choosing an (EDIT: external) account-recovery method?
The flip side to allowing account recovery at Google’s discretion is lessened security for everyone. (Obviously not black and white. And I agree Google should have flexibility for old accounts. But it’s an odd thing to reject a major provider over.)
They did have a method to recover their account that they tried, though - they said that they used the account recovery codes, but that they were rejected. (Those would be the codes that Google gives you when you initially set up 2FA.)
op said they had recovery codes but they didn’t work.
You can have all the right details and recovery methods but if at some point they request you to provide the code they sent to the phone you don't have for the last 10 years......... That's it.