At Lavaboom, we simply check against the 10k most used passwords (in memory), but we plan to move to 1 million soon (on disk – account creation is relatively infrequent for the slower access speed to not matter).
Our problem is that we SHA the passwords on the client side, so each password is 256 bits long. The resulting hashtable (or bloom filter) is still a reasonable size for disk storage, though.
We SHA256 the passwords on the client side at Userify (SSH key management for EC2) as well (bcrypt is too slow in mobile browsers), and then bcrypt on the server side the resultant hash. (We don't cache it, though.)
Even in the event of a TLS leakage, we still never see your original password, and the server doesn't end up doing any more work. It's not perfect, but I definitely agree it's a great step forward.
Our problem is that we SHA the passwords on the client side, so each password is 256 bits long. The resulting hashtable (or bloom filter) is still a reasonable size for disk storage, though.