Actually, it's pretty simple - each time you login, check that the password (now cleartext, as supplied by user) is valid AND meets the current requirement. If

Actually, it's pretty simple - each time you login, check that the password (now cleartext, as supplied by user) is valid AND meets the current requirement. If it's valid and doesn't, push in to a change password flow with the current requirements. If you're extra careful, you can expire older passwords and require an email reset before use.