> Back then and still now, I think Google need to make it easier to handle this situation. Strong end-user support in these situations is hard because genuine fraudsters will happily file support tickets and socially engineer support to get their accounts back - I even witnessed auto-generated pleas to support once.

How much are accounts currently worth on the market? It seems that making the recovery procedure more expensive than the worth of the account should resolve that issue. At the same time legitimate users are probably willing to invest some money in order to recover their account.

For example offer a $20 option to send a registered letter to an address provided by the user. Then Google can check if: 1) The name on the credit card matches the name on the account, 2) a given address hasn't been used too often, 3) the identity check done by the postal service (checking if the recipient actually has a given name) succeeded.

This won't be a perfect solution and there are definitely edge cases for which it won't work (in countries without registered mail, if someone doesn't have a credit card, etc.). But it should be able to cover the majority of cases where legitimate accounts have been locked.