I've occasionally written comments about the difficult of achieving proof-of-useful-work mechanisms and I should probably find or write a standard post about this question.

In order to be as decentralized as Bitcoin and related PoW mechanisms, a proof-of-work mechanism should have

* the ability to create an unbounded number of instances of the problem deterministically from numeric seeds

* the ability to scale difficulty up and down using a difficulty parameter

* in a way where anyone can easily confirm that a given problem instance corresponds to a given seed, and anyone can easily confirm that a given solution correctly solves a given problem instance

I'm not aware of a proof-of-useful-work mechanism that meets these criteria. (I'm also not aware of an argument that it's impossible to have one. Zero-knowledge proofs might actually go far toward making it possible in the future. but it's kind of complicated.)