Is there a way to set up proof-of-work systems so they would be even more useful? One of the arguments made against Bitcoin's design choices is that it wastes resources authenticating transactions. In particular, finding small hashes is completely useless for the world. 

Are there approaches (or other crypto-currencies) that use proof-of-work by working on some useful difficult problem? There are plenty of projects like SETI@home or Folding@home that distribute difficult but potentially useful calculations among different users, is there a way to use such useful calculations for building a proof-of-work system in a crypto-currency, or is there a fundamental reason (economic or computational) that a proof-of-work must involve useless work?
I think the premise of the question is not correct. The work is not useless, it secures the transactions. The public hash chain ensures that Bitcoins can only be spent once. The mechanism piles computations on top of legitimate transactions so that the recipient knows that an attacker would need at least as much computing ability to "undo" the transaction.

There is currently no known way to make the work more useful. The problem is that the primary purpose of securing transactions imposes a number of requirements on the work done:


The work must be much, much easier to verify than to do. So it pretty much has to consist of searching for something rare, doing billions of searches to test if an input has a particular characteristic. That way the verification simply requires confirming that the input you found has that characteristic.
The work must in fact secure the transactions and not be severable from them. If I see that you sent me 10 Bitcoins and then billions of computations are piled on top of that, it must not be possible to remove that transaction and then pile those same computations on top of a conflicting transaction. So you can't use the result of an arbitrary chunk of work to prove work on the Bitcoin chain.


It's hard to imagine any additional useful work that could be accomplished while still meeting these requirements.