Like most sites, after you register your account, we generate a nonce and email it to the provided address. You click the link with the nonce, we prompt you to set your password, and your account is ready. Our bug was that for already-verified users, the nonce column in the database is empty (it's a nonce, you see, so we only use it once...). This was the root cause for both bugs Mr. Sclafani describes.
User.find_by_email_and_token(params[:email], params[:token])
I'll also add that while we had tests that were intended to avoid this bad behavior, these tests were unfortunately broken and were instead verifying the incorrect behavior.
Instead, the user is emailed a token that's just her user ID, HMAC-signed with the last login date and a secret site key.
You can't generate valid reset links without knowing the secret key and you can't tamper with the one you got because it's HMAC-signed. By adding the last login date to the HMAC you make sure the link can be used only once. After a user resets her password, the last login date is updated to now so the link is no longer valid due to broken HMAC.
I like this solution because it doesn't rely on storing any state anywhere between requesting the reset and completing it.