I was reading this question and got myself thinking - why can't a crypto-currency use as proof-of-work a difficult problem that has value outside of the network? I understand the effort to produce all those hashes is not completely "useless", but still it seems like too much electricity consumption just to secure a crypto-currency - a proof-of-work that could produce a valuable by-product would be much appreciated, I think.
So I was thinking, what problems could there be if proof-of-work were, say, the factorization of Mersenne or Fermat numbers? Validating a number's factorization is relatively easy, compared to looking for the factors. And a crypto-currency based on it could give an big bonus to finding a Mersenne prime, and a mega-enormous bonus should a miner find a new Fermat prime (assuming there are some more), for these are intrinsically valuable even though validating the discovery would also be incredibly heavy, computationally speaking...
Appart from the obvious problem of difficulty being uncontrollable and going always up, (might be solved by allowing less profitable blocks be mined using another proof-of-work), I thought of the case where a country gets disconnected from the rest of the Internet: In current bitcoin this means coins mined there during the disconnection are lost after the country's reconnected, and any merchant accepting those locally-mined coins will lose their money.
In a system aiming to have a useful by-product as proof of work, all discovered factorizations should get eventually accepted, even if they were mined in such isolated conditions or were initially included in a blockchain that happened not to be the longest - unless some other miner discovered them independently and included them in a longer blockchain.
But then I realized this system could mean miners could attempt using this proof in more than one blockchain - I guess this would open the door for some types of fraud.
Could it also lower difficulty for double spending attacks? What other problems could arise in a system of this type? Are they intrinsically unsolvable?
The same could be said of using protein-folding, or analyzing SETI@home packages as proof of work...