A relevant answer from last year by @schoen (upon which I stumbled recently): https://news.ycombinator.com/item?id=22495700
The arbitrarily parameterized instances part is really important. In Bitcoin this is done by feeding prior blocks as input into the hash and then getting the hash to match the adjustable difficulty value, so you can generate new problems automatically based on the history.
The Stack Exchange answer that someone linked to here mentions this issue by saying that, if you just had a generic and deterministic useful problem, people could precompute solutions to relevant instances of it, which would amount to premining on the blockchain.
The "doing work to verify transactions" aspect comes in when you can make the problem instances actually encode a specific version of history. It's not obvious how to do that where each and every instance would be of intrinsic interest or value to someone.
Maybe there's some kind of physical simulation where this could be the case (like, each individual hash represents a particular randomly chosen chemical from a very, very large family of chemicals whose properties are being explored by simulation in some way, or something), but I'm still not sure how you could then make a successful result be easier for other people to verify without repeating the same amount of work. (I'm not familiar with a technique for proving, in an easily-checkable way, that the result of a complex physical simulation was such-and-such.)