Can mining puzzles be made socially valuable? Bitcoin miners work to solve a random puzzle as "proof of work".  A huge amount of raw computing power is going into finding the solution to these puzzles, yet the actual solution to the puzzle serves no purpose other than to demonstrate that whoever found the solution has access to a great deal of computing power.  Can the bitcoin protocol be modified to accept puzzles from the real world who's solution would actually have some social value?  Perhaps some scientists, governments, or corporations would be willing to pay some amount to whoever solves some reasonably complex computational problem first, and they could contribute some BTC towards the reward a miner receives.

I understand that the particular puzzle chosen is very clever, particularly as its complexity may be easily adjusted as needed, the solution is well defined and easy to verify, and there's virtually no limit to the creation of new puzzles.  I just wonder if something even more clever could be incorporated, if someone ever manages to come up with it.

To clarify, the analogy I have in mind is the way reCAPTCHAs have virtually replaced traditional CAPTCHAs, substituting socially valuable book digitization work for a socially useless text-guessing exercise.
To be valid as a proof of work a problem needs to


be difficult to produce, and it's difficulty must scale up and down as the network speed requires. The levels of difficulty must be quite granular, bitcoin's go down to several decimal places to ensure an even blocktime.
have no central issuer, the work must be independently creatable and verifiable. No central authority should be needed to produce problems and solutions.
be quick to verify even on microprocessors, every node in the network must verify it 300,000 times over to synchronize with the blockchain today. Currently I can verify a sha256 merkle tree proof on a processor that costs a few cents in bulk;  scrypt coins are almost useless in that you need a huge amount of memory to verify the proofs. 


Nothing else can fit this bill at all. Primecoin attempted this, but it's method has removed the ability for SPV clients to operate (kilobytes of stupid number strings in the block headers), and the work it produces (certain types of prime numbers in a sequence) is merely a curiosity rather than anything usable by anybody. 

It must be a cryptographic hash. The simple fact that it is protecting the network means that it is not "useless".