I had this same issue with a very odd and demanding client. The site was a company intranet, that could be accessed via a VPN for telecommuters. One of the requirements (it was written in bold):
Password re-set mechanism should be convenient and not rely on e-mail. Re-set requests must be granted conveniently and require evidence that the site trusted the visitor prior to the re-set request
What I ended up doing was generating a Manderbolt (100x100) for the user to download as their 're-set' token, along with some secret questions that they would have to answer. To change their password, they would have to answer their questions and upload their fractal (the quadratic plane was defined based on their private information with simple hashing to avoid collisions).
This satisfied a requirement that password re-sets had to be based on what they had as well as what they knew. If they lost the fractal or forgot the answers to their secret questions, they had to appear in person to have the password re-set.
Not exactly bullet proof, but it satisfied the needs at the time. The challenge was making the fractals unique (at least 30 pixels unique), since most users shared a lot of common private data (city, state, area code, etc).
Edit
The fractal (rather, a one way representation of it) was used elsewhere as well. Think RFID + camera.