The way I see it resolved is for Google and Apple to link the accounts to a physical person via government ID so that if you want issues to be resolved you'd have to verify yourself. This would also limit abuse by bad parties.

It would be easy to fix this problem simply by charging a hefty up-front fee for direct connection to high-level human support, who will take the time to verify the user's identity using established KYC procedures and then take action to restore the account. The fee would then be refunded if the problem turned out to be on the company's end.

Companies like Apple don't offer that, because they don't GAF.