please correct me if I'm wrong: you are not storing passwords, you are storing hashes & salts. One different long random salt for each password.

In my database I store hashes obtained with Blowfish:

http://derekslager.com/blog/posts/2007/10/bcrypt-dotnet-stro...

How many tries would you have to do to guess it? And for the other passwords you have to start all over again.