I have to think that the reason sites don't employ reasonable password encryption has nothing to do with computational cost, and everything to do with poor software design. There is far more computational cost introduced by the encryption and decryption required for SSL traffic than there is for the once-per-session hashing of a user-provided password to compare to the stored hash. But it it takes a bit of thought and effort to research, design and implement password security.
On a different note, if any of those sites utilize credit card billing then I would be much more worried about a breach of that data.
The Russian website was most likely full of sluts, and the other 5 million with passwords like 111111 most likely did that because they joined the site to see who was available. Even though he got 42 million passwords, what is the chance that he will be able to have the Time to mess with 1 to 5 thousand passwords?
SALT can be anything that is added to the password before it gets hashed. Could be part of a user ID, birthdate, account #...etc or a special secret "key" that only few handful people knows. That is determined who wrote the password portion of the software.
I for one have done this for a company and it's really easy to do. Just have to keep it close guarded secret and test it to make sure it works properly.