I think your statement is too broad. I agree that it wouldn't work on the web, for the reasons that you state. But it is a useful approach in a lot of other situations. For example, I've seen it used successfully in gaming to prevent DOS attacks.

Client Puzzles have a couple nice properties: the difficulty can be adjusted & they can be implemented in a completely stateless manner. The last point is the most important because it what protects against a [D]DOS attack.