Re: password specifications..
Would it not be possible to hash each character in your password, add a slat to it as well to make it a bit harder to brute force if the DB bacame compromised.
Unfortunately, that's barely better then storing the password in the clear, since there aren't many different characters (OK, including all of Unicode takes it to ~10^6), and you'd be able to find the password character by character - in parallel if you want.
The interface for a system to store passwords, issue challenges for certain characters, and validate the response seems fairly simple, which should make it much easier to develop a secure, isolated system for this purpose.
In other words, in this case, making sure those passwords won't leak seems achievable, with reasonable care.
However, the implementation also seems like it should be fairly simple, which ought to preclude the sort of issue in this story...