[jcrites]

Actually, I think there is a technical solution. Say that the password system keeps a complete history of a user's plaintext passwords, stored encrypted using the current password as a symmetric key. Administrators cannot access this password list without the current password.

When a user changes his password, he enters the current password and a proposed new password. The system uses the current password to decrypt the list of previous passwords. It checks the proposed password against the list. If accepted, the old password is added to the list, and it's encrypted using the new password and stored.

Are there any threats against this scheme, or will it work?