You are unhappy that people will reserve PublicID's and not use them. This practice is often called "domain squatting" by those unhappy that the name they wanted was unavailable to them when they wanted it, even though nobody seems to have an active site using that name.
However, your proposed solution is to have randomly generated strings, or even some sort of changing hash. I really hate the changing hash thing. It seems like hand wavey, "we'll work out the details later", added complexity, that will lead to huge network load and dead URL's that point to hashes that have changed after the URL was created.
As for the randomly generated strings. You'll get those. When all the memorable PublicID's have been used up or "hoarded" by "squatters" (Central Bankers in Australia call old people who save their money, hoarders, by the way) . When all the memorable PublicID's are gone, you can always generate your random string. So we'll get there eventually, if that's what you want. But even then, I can preface my random string with my initials or dogs name, or something to still make it a bit unique. Isn't the ability to make it at least slightly unique after all the evil squatters have done their worst, still better then starting off with a system that has no uniqueness at all?