Blockchains only work by probably wasting in order to build a history. If you aren't wasting, then it wasn't expensive to build the history (it was subsidised), and it wouldn't be expensive to build a different history (that one could also be subsidized)
It's possible for something to provide a social benefit but not make sense for anyone to pay for as a for-profit business because others would get the same benefit and free ride off them. (Hence the problem of public goods in economics.)
So if the proof of work is only solving some general research problem, then it might not be feasible to double dip like you've described. That's why primecoin was able to avoid the problem.
I've seen partial schemes for this, but no complete ones that would justify implementation. If a full and workable scheme could be devised, I would bet on it replacing sha256 based proof of work, eventually.
Edit: See my here for a model of how NP complete problems could fill the role of you could predict difficulty in advance. There wouldn't be double dipping because the person wanting the answer wouldn't pay both bounties.
My unprovable guess is that any other non-sellable problem will ultimately have the same outcome. It's interesting and useful for a bit, but when you have a billion dollars of hardware grinding nonstop for years in a row, you eventually exhaust everything interesting about the original problem and then it's back to the same waste you started with.
If you attack the network you can steal billions - so if you have that much computing power available for your useful work, you can temporarially use it against the block chain.
As long as that mining power is available anywhere the chain isn't secure.
