I said that the random salt is stored somewhere; I made a point of saying it's usually stored alongside the hash in the database.

The hash can't be changed in a set-time process. As you said yourself just now, you would have to ask each user to reset (or just re-enter) their password the next time they login, use the old salt to make the hash and match it against the hash in the database, then use the new salt to make the new hash. I use the word calculate because that's what you do to generate rainbow tables (use the hash function to 'calculate' the hashes of plaintext strings). And yes, you do have to trust the hosting company, but I haven't seen many companies that I wouldn't trust. But that applies to everything you do with your site.

Many of the sites I see do simply store hashes in cookies and then match them against the hash in the database. This seems to be decreasing luckily but still exists in some publically available systems.

I pointed out that if the salt is discovered in a static salt situation, that you are then left with only an extremely slightly slower program to find the original plaintext password, as it's not difficult to make a program that prefixes all the passwords in a brute-force or dictionary attack.

And my point was that either methods are good. The static salt must first be discovered. More often than not, security is compromised on sites and the attacker is left with only access to the database, whereas they won't have the salt which is hard-coded into the PHP file. It's a matter of choice.