It's 3am and I've been drinking, but this seems feasible: When the user changes their password, encrypt the old password with a key derived from the new one (you have both in plaintext at this point, when entering old/new passwords). Then hash the new one as usual.
Then when the user goes to change their password again, you have the plaintext of the current one, which unlocks the previous password, and so on back in the chain. You can then compare the new password with previous passwords for similarity.
The method I am about to mention here is based on that which was outlined earlier by somebody else [1]. As I will mention further down, the method I suggest here will give the administrator and the CEO the opportunity to conspire and retrieve users passwords without the affected users knowledge, but I will here assume that such could not happend and that if they really wanted to do so, they could find other means anyway (keylogging, etc.)
First time: On his client, the user is asked to enter a password which is checked to comply with password rules. This password is salted and hashed before it is stored on a central machine.
n-th time: On his client, the user first enters password "n - 1" which is then salted and hashed and sent to the central machine for comparison. If hashes match, you may enter the new password "n" which is checked to comply with password rules.
Password "n - 1" is then encryted with password "n" and stored on the central machine. Password "n" is stored on the central machine in two forms:
1) Salted and hashed.
2) Encrypted with a public key.
Password "n" is encrypted with a public key and stored on a he central machine. Also, when this machine stores the new public key encrypted password, it deletes its own records of any previous public key encrypted password for the user in question.
Through recursion, all old passwords ("n - 2" ... "1") are decrypted and the new password is checked so that it does not match any previous password and that it is not a simple permutation of any of those.
If the user forgets his password, the administrator physically logs into a machine which is very tightly secured. This machine does not allow inbound connections of any kind over the network and can only make outbound connections to the central storage machine. Furthermore, the machine does not allow the usage of any removable media (CD, DVD, USB stick, etc.). The drives of the machine in strongly encrypted, as is the private key which is stored on this machine. In order to decrypt the disc of the machine, two passwords are needed. One of the passwords is held by the administrator, the other by the CEO of the company. The same goes for the private key which also has two passwords, both of which are needed to decrypt it. Thus, two people must be involved in order to decrypt the password for a user. Once the administrator and the CEO has logged into the machine, they connect to the central storage and retrieve the encrypted key for the user and then they open their shared private key and decrypt the password. After the user has been given his old password, he must create a new password following the procedure described above. That way, the administator and the CEO does not know the users new password (unless they conspire to do so, but that would be breach of trust).
Proposing that any 'forgotten password' reset requires the physical presence of the CEO and a sysadmin at a dedicated machine is a really good way to ensure that within six months all passwords are either stored in plain text or written down on a post-it note.
Then when the user goes to change their password again, you have the plaintext of the current one, which unlocks the previous password, and so on back in the chain. You can then compare the new password with previous passwords for similarity.