I think the fundamental reason for the wasteful computations is the 10 minute bound. It has turned out that the difficulty of the sha256 problem can be varied easily. What other computations that do not involve a third party (like Folding@Home) exist in which the time to solve the problem is predictably related to some integer?

Even if you would use Folding@Home or world community grid. What would happen if Folding@Home stopped existing? If you want to change the problem, you would need to have a way to vote in a distributed way over another computation to be performed with some piece of code for the verification of the work performed. This is in principle possible, but how are you going to get an agreement on which particular piece of code? I think all of these have solutions, but they require work, where bitcoin as it is now is pretty solid (until someone breaks sha256 (which will surely happen before the last million coins is generated)).