[umsm]

You can ask for the old password and the new password twice. Solves your concern without storing anything critical.

[DonHopkins]

Also: "Must not have been used within your last 20 passwords."

So you just have to provide your last 20 passwords.