As we all know, a typical password validator formula is a great way to encourage people to choose "Secr3t!", or something else equally bad.
I'd really like to see a password field that auto-generated pass phrases using full english words from a sufficiently large wordset (in the vein of "correct horse battery staple"), possibly even enforcing such phrases as the only valid type of password. Every user gets a strong password they can actually remember. (...although possibly a non-starter for mobile contexts.)
Why not try to generate semi random pronounceable passwords? There's a clear decrease in entropy but brute force cracking against all pronounceable strings less than 20 chars will still be hard. (Of course your definition of pronounceability might differ.)
I don't think that's it, I think it's just to annoy people into changing it.
* hash current passwords with a salt, unique to each password entry, and throw away the plaintext entries.
* keep a history of hashes per user, to prevent changing to a past password
* ensure fair complexity of the incoming password
* once the deadline has been reached, force users who have not yet changed their password to do a password reset via an online form
* never, ever again think that doubling a password is a proper way to fix a security issue, ever...