In Germany every service that you can sign up for online but requires proof of who you are uses something called "PostIdent" -- and its a service offered by the post office where you take the form in with your passport (or ID card) and they punch all the details in the computer and 'verify' it's you. In a (more) secure future, I see this being the real password recovery mechanism. The other technique used by online banks etc... is to send your password reset to you by mail. This assumes that physical mail to your registered address is more secure than online quizzes.

I think both of these options will become the standard for anything where security matters.