In short, you can send their Data Protection Office a letter demanding access to your data. In my case it took almost three months but they eventually relented and reset my password. I guess a lawyer could have gotten it done faster, but who knows.
Did they ever verify the you had the old password / recovery email like you offered? It seems strange to me that they reset an account password because they got many letters asking them to.
All e-mail communications were sent through the same address I gave as recovery address, so they didn't have to ask. It is possible that one of their e-mails was sent to my recovery address instead of my personal address, but since they are the same account I wouldn't know.
https://7c0h.com/blog/new/lost_gmail_ii.html
In short, you can send their Data Protection Office a letter demanding access to your data. In my case it took almost three months but they eventually relented and reset my password. I guess a lawyer could have gotten it done faster, but who knows.