Firstly, there is Google's solution, which is to become physical.
An option to recover the password is to be sent a code to a previously registered and verified cell phone. When you want to reset your password you get a text message in your cellphone. You are taken to a page that, upon entering the right number, takes you to the password resetting form.
Another solution is the questions: the user chooses and/or writes, two or three questions that he can easily answer but hackers dont, like what was the color of your first car. Provide a list of questions, and also allow the user to write his own, maybe in his own language using their special alphabet.
This can be mixed with questions like what is your identification number where USA people can enter the SSN and we argies the DNI.
The idea is to get physical, that is, require the user to show knowledge about something that's outside the virtual world where an impostor can move with ease.
For example if you were an airline ticket online seller, you could ask the user where did he travel to the last time.
To avoid dropping users you should exhibit some elasticity, like allowing the user not to remember very well the last trip and answer instead with the previous one. In this case you display a list of random answers that also contains the right one.
In this type of interactions it's important to brainstorm many use cases that might show over time, and implement a design that will work in most cases.
The 300 million button case is an example where the original designers didn't consider cases like one that comes back after a long while and doesn't remember his data very well. Like, the email address of 4 years ago.
For example, recently I was asked in which month did I change my password. Not the slightest idea ...
It is good to offer options, as Google does. Like, text message or questions.
If you are going to be elastic, allowing for some lack of precision in the user answers, you should brainstorm a minimal level of certainty like 3 out of 4 where the good answers must include at least 2 of the most difficult to fake.