To get around this, some sites ask the user for a hint question when they register. If the user forgets their password, they must answer their hint question (which they hopefully still remember), and supply some other personal information (which is verified against the info they provided upon registering). A new password is generated and emailed only if the above are correct. I'm pretty sure Yahoo does this for My Yahoo, Yahoo Mail, and the like.

Another idea would be to generate a new password, but revert to the old one after, say, ten minutes if the user doesn't log in and change it. In this case, you would still let the user log in with the old password within those ten minutes. I realize this might not be easy to impliment ontop of an existing username/password database, though.