TPTB interesting... it seems I came up with a similar objection against Ethtereum independently after you. I think we could have a  "computation-coin" as suggested in my OP(3), which does not have this issue. Do you have any thoughts on that? (Ignoring issues that all coins have?). The main issue with this computation coin of course is how to prevent someone from stealing a solution. That needs cyprography more advanced than bitcoin, if even possible.

I was thinking along these lines.

1. Someone posts a checking algorithm to quickly check any possible solution for a problem he has (e.g. a SAT instance).
2. He adds a public key; solutions need to be encrypted with it.
3. Somehow it must be possible for everyone to check that an encrypted solution is correct (unless there's a pre-hash collision, in which case someone who finds that can falsely state he has a solution and get the coins. There's nothing to do about that, but it might not be a big issue, because finding the solution should be easier than finding a prehash).
4. The poster of (1) can decrypt the solution using his private key.

Then we're facing (3) and we also still need to add that the address of the solver should be posted and be in the encryption (otherwise they can still steal the encrypted solution).