I'm trying to solve that exact problem with Scicoin (
http://www.scicoin.org )
My solution to the problem involves a bit of social trickery and a new (non-?)"economic" model.
The idea is to keep the proof-of-work as it is, completely useless, but, have the network "detect" that a block has been "mined by science." When the network thinks a scientific institution found a block, it multiplies the reward by 10,000. Then there's a social contract: scientific institutions should only use these coins to reward useful computing work done by people who donate their computing power to solve useful problems, at the same approximate rate that "mining" the coin itself would reward the users. E.g. if you would earn 1 coin for 1 petaCHOP (Coin Hash OPerations) of work, you would also give 1 coin for whatever cure for cancer computing effort you put in that's roughly equivalent to 1 petaCHOP. The scientific institutions would not spend these coins otherwise (i.e. let them rot). This way for ever X computing effort to "mine" the coins, OVER 9000 times that can be spent on useful work and you still get coins for that AS IF you were mining them too.
The way the network detects a "Block Mined for Science(TM)" is by checking whether there's a pool mining more than half of it. The network simply assumes that whoever mines the majority of the coins is a pool that serves scientific projects and that it does the right thing.
And about the "not-really-a-coin" aspect: the coins are unlimited and you get paid by the hashes you put in, forever. To avoid runaway inflation we can simply use Freicoin's awesome "coin rot" feature (i.e. use it or lose it).
The whole idea is for the system itself to NOT be "money," that is, it is not to be confused with a vehicle for "storing wealth," for the current cultural definition of "wealth." With this, it becomes possible to have a simple "10,000x" reward heuristic based on a simple no-stress honor system. If it is exploited, oh well, no problem, just reset the game or try something else.
And the coins are unlimited, there's no end to mining and therefore no end to the toy-incentive to contribute to science.
And Basic Income was a huge motivator of this whole train of thought. Interesting that that was mentioned in this thread too.
Didn't know about gridcoin, curecoin. Will look into them.