Given no restrictions on password format (other than that it has to be a certain minimum length), many people will use actual words or combinations of words as their password, which aren't terribly hard to guess. Those who make their password more complex will just go back to writing it down, and you have the same problems you did with an 8-character password.

It all boils down to one basic fact - the more difficult it is to brute force a password, the less difficult it is to get your hands on it through social engineering. I still say that a short password with lockout on double failure is more secure than any long password. Just be sure to encrypt it using a different key for every user (registration time + user name + some overall server key, perhaps), or someone with access to the database could match their hash to the hash of every other user, and gain access to people with the same password.

There's also the little matter of people tending to use the same password everywhere, which means that while your security may be infinite, the next place over could leak passwords like a sieve. This is another reason to assign passwords rather than letting people choose them, which means in turn that a short password is better than a long one.