It can't be made useful because the output of a useful calculation can't be known in advance - otherwise it wouldn't be useful.

I think Gridcoin offers a happy medium. It's proof of stake, but it also offers rewards for participating in BOINC-based research projects.

https://gridcoin.us/

Not exactly "proof of work" in the same sense its being used, but I wish that the project would get more attention.

I've been trying to get people to pay attention to this project for years. I think a lot of the "useful computation" chains are much more likely to survive the next cryptocurrency crash because of their inherent utility. For example, the various storage coins, stuff like Nym or Oxen, Namecoin, etc.

You can gain use computing to gain specificity from complexity though, and recognize that new specificity - i.e. brute force protein folding calculations.

That would be great, but unfortunately the structure of problems that are well suited to proof of work (hard to compute but easy to verify in a decentralized way) doesn't seem to have too many practical applications.

Aren't there lots of NP problems that have this property?

Yes, but how many of them are distributable in the way required by the constraints of mining? (I really hope I'm wrong and would love to see a counterexample of "constructive" mining!)

All of them, by definition.