All of those problems could be solved, if instead of using Proof of Work from the Script, you check your Proof of Work from your transaction hash. Then:
- It cannot be stolen, because modifying the transaction in any way (when it comes to legacy parts) will lead to a different transaction hash.
- It can be used once, or thrown away. If you include transaction with one hash, you cannot include it again (there are some quirks, when you reuse the same coinbase transaction in some future block numbers, but most of the time, the system is resistant to duplicated future transaction hashes: if you can duplicate transactions, then there are more serious issues ongoing, like “history flood attack”).
- If the size of the whole transaction will take 80 bytes, it will be compatible with ASICs. That part can be achieved for example by using different sighashes, like
SIGHASH_SINGLE | SIGHASH_ANYONECANPAY, and then require for example z-value of the transaction (hash of the signed message) to contain some leading zeroes. - Also note, that it may be possible to claim N coins at once, by producing a sufficiently huge Proof of Work. Then, you share for example transaction like this one, and then you claim 10 coins instantly, without providing separate proofs for each and every input. You just claim them all by providing sufficiently low hash in the whole transaction.