In response to Tom Moertel, using a generate random salt function is exactly what you do using encrpytion. However, you also need a way to log into the system.
Please remember that in order to log in, the user submits their password to your service, and it does the exact same thing it did before.
salt = generate_random_salt()
hash = md5(salt + password)
compare this hash to stored hash and if they are the same user is authentic.
Problem is, you need to use the same salt as before or no one will ever be able to log into your service.
Where generating this salt becomes very important is when setting up encrypted communications. Let say for example each time you set up your encryption, you use the same key, and encrypted communications always start with the same thing.
To make it simple we do an encrypt('helo other server, we'd like to establish encrypted communications'); which returns 4fc3d2. Now if everytime you set up this encryption, you do the same thing, the bytes you send over the network are also the same(4fc3d2). This is where your salting and IV (initialization vector) comes in. since then all you do first is encrypt(salt), then encrypt(handshake message), and the bytes sent over the line will always be different. This makes it much more difficult for a crypto-analyst to try and deduce what you are sending without decrypting any data.
This is why I proposed you use an actual encryption algorithm, and not just a hash. You want to take advantage of the fact that everytime you start encryption, with the same key, you always return the same result. Now you might want to pass your encryptor 128 or 256bytes to be more secure, this is where your hashes come in since you easily get a fixed length password from a mixed length password. So you simply do your md5/sha(password), then encrypt it against your private/public key pair with the pirvate key discarded. There is literally no way for your average attacker to decrypt these passwords.
The biggest worry from myself would be that with spammers and cracker's getting increased computational power through botnets, cryptoanalysis could become alot more prominent. Which is why I would also recommend you rotate the key's used ona yearly/monthly/daily basis, and force a password change yearly. (if you database is compromised, they have a copy of it, even if it takes 10 years to decrypt it.)
Check out the RSA Challenge: http://www.rsa.com/rsalabs/node.asp?id=2093 And see what using distributed computing can do to break these passwods.