Verify keys are not too similar

so this it the mitigation that @udidahan recommended. the problem is that not  being able to reproduce the issue (cant find too keys that cause the problem) i dont know if the "string being encrypted" is a variable that impacts the outcome.

Can anyone come up with anything better?

For reference here are the SO articles 

 * http://stackoverflow.com/questions/1556683/does-rijndael-always-throw-an-exception-if-the-password-isnt-correct
 * http://stackoverflow.com/questions/5812232/c-sharp-aes-rijndael-detecting-invalid-passwords
I may be wrong here, but shouldn't our verification for similar keys be just against the new key?
So what I'm saying is, user is going to move the existing key to the list of ExpiredKeys and then add a new "master" Key, so all we should need to do is validate that the new "master" Key is not too similar to the ones in ExpiredKeys.