I think I have a "legally safe", but slow, solution:
1. The user requests information about them but claims that they lost the password and the email address.
2. The company sends a form (in English) that basically asks for the information on the id (name, date of birth, etc) and the information being requested (ex: password reset).
3. The user prints this form, fills it out and attach a copy of their ID.
4. The user goes to a notary in their country to get the signature and ID verified.
5. The user sends the form to the client's country Ministry of Foreign Affairs to get the notary's signature verified.
6. The user sends the form to the embassy of the company's country to get the Ministry of Foreign Affairs seal/signature verified.
7. The user takes a picture of them holding the form and sends that picture via email or similar to the company.
8. The user sends the form via snail mail to the company.
This process can be shortened if both the company's country and the client's country have ratified the Apostille Convention, formally known as
the Hague Convention Abolishing the Requirement of Legalisation for Foreign Public Documents.