"I think Andreas Krey had a very good sugestion... You overelooked that he suggested to throw the private part of the key away!
This will give you a good one way function, since there is no way to recover the original without the (deleted) private key."
I don't think that using public-key encryption here (which is de facto precisely reversible) instead of hash-based encryption (which is essentially one-way) is the answer.
Consider the simple case of just adding a little "salt" to a password. Say, I start with password ABC, add "~!" to the start of it (like I said, simple!), and hash "~!ABC".
When the rainbow hash algorithm comes up against this as an unsalted password, it might come up with "~!ABC", but it more probably will come up with something wholly unresembling that original salt+password combination, like "XYZ$". If he knew that the "salt" was in the first two letters, he'd use "Z$" as the password, which wouldn't work (because the hash of ~!Z$ is not the same as the hash of ~!ABC). If he knew that the "salt" was "~!", then he'd still be nowhere unless he made a custom rainbow hash with the constraint of every passcode starting with "~!" (then he might come out the other side with "($" as the password, but only if "~!($" and "~!ABC" hashed out the same).
Now, IF WE HAD PUBLIC KEY ENCRYPTION, the above would not be true at all. Rainbow hash brute forcing would still work, although the stored length would be longer and so the hash would be significantly larger. But, it would ALWAYS come up with "~!ABC". So, if he de-hashes 10 passwords, the pattern of "~!" as a prefix will be blatantly obvious, and the "salt" completely useless. For every password yanked out of the algorithm, he'd just chop the "~!" and use that password for authentication.
Now, of course, the problem with the simple prefix (or simple algorithm creating the prefix) is that when it is known the hacker can just create a new rainbow hash with that prefix or algorithm as a constraint. The random salts make that more difficult. For instance, even if he knew that "~!" was the salt for this particular password and created his rainbow tables based on that, he wouldn't gain anything because the next row's salt is "#$" and so he'd need a new rainbow table, etc.
Personally, I am not a security professional, but I'd think that a combination of tactics would be the best. Start with a random seed (stored alongside the hash in the logins table). Add to that an algorithmic seed (an MD5 hash of the second, third, and fifth letters of the user id or something similar), which doesn't get stored in the database (so, to find this second salt the hacker would need access to the code in addition to the database). Then add on the password the user passed in.