How to design a site that prevents users from creating weak passwords

I found the heart of this gem in the FAA's Advisory Circular AC 120-78 "Acceptance and Use of Electronic Signatures, Electronic Recordkeeping Systems, and Electronic Manuals" - at the top of page 8, specifically.

In short: don't permit any two users to have the same password.

My first thought upon reading that is that I'd have to store plaintext passwords for every user in order to accomplish it, but that was foolish of me.  It's easy to check for duplication in exactly the same way that a users password is checked against their username during a normal login - SALTed hashes pose no problem.

Whenever a user creates or changes a password, check it as the password for all other users, against all usernames, and against a dead password list.  If there's no match, they're golden.

If you do find a match, three things must happen:

1. The user doesn't get to use that password (obviously)
2. The other users with the matching password get flagged as having insecure passwords.  These passwords can be invalidated and an email sent with a code to change the password on the next login.
3. The bad password is added to the list of dead passwords.

Even with no other safeguards, this means that you'll have at most 1 user with any given bad password, which goes a large way to defeat dictionary attacks.  It has zero cost for users that create good passwords to begin with.  Bad passwords are removed from the system automatically, even as new patterns emerge.  The cost to implement it is minimal - it reuses existing techniques.  The dead password list can be initialized with common bad passwords in advance, prevent most people from picking poorly to begin with.

There's always some cost to having your users actually use good passwords.  Obviously, it would be easier for them if everyone just used "password123".  If you accept the effort of creating a password that is actually unique across your site as an acceptable requirement, then there's no reason not to use this system.

The best part is that there are no arbitrary limits on number or types of characters, which is a huge point of frustration for many.  In fact, choosing a password is no different than picking a unique username.

I just don't understand why I only see this languishing in this FAA document, of all places.