Password Reset instability

The password reset functionality seems to be unstable. We have customers complain from time to time that they are unable to reset their password or they get an error message saying “This is not a valid password reset request…” It appears like the token generator is slow some times (not always) and the email gets sent to the user before the token is generated. Is that possible? Anyone else having the same problem.