Lance James wrote an interesting piece on how to train users to use better passwords. His idea of setting password expiration based on the complexity of the password is a very good one. This not only educates users but also negates the need for organizations to have a single static password policy. Password policies tend to be problematic, since others like to litter their passwords with special characters (!#?) while others prefer using longer, but more easily remembered passwords. It's difficult to create sane policy which covers all cases.
I would however argue that for pavlovian training to happen, the users need instant feedback based on their actions. If the user is not warned beforehand about the consequences of their new password's quality, they will only get frustrated if they're required the change the password after just a few days. As they should.
How about we just switch strength indicators to expiry indicators?
So instead of telling the user they chose a bad password after they've changed it, we could give them direct feedback to how long they can use the new password for. This gives the user the chance to optimize their behavior between easy-to-remember vs difficult and fast expiry vs stable. We would no longer need to train the user: this mechanism would make the effect of password complexity immediately clear to the user.
The above quote on how developers fail to teach the users hits the nail on the head. The failure of most password policies is that they've been opaque and people have wanted to pass that hurdle with as little effort as possible. Switching away from static policies and abstract strength indicators to tangible variables in a language the user can understand should push us to the right direction.