http://www.proofofexistence.com/

and

https://github.com/spesmilo/sx/blob/master/src/sx-embed-addr

Embedding data in the blockchain as a hash is out there and a reality.

I suggest that there should be a new payment type that is unspendable to support this.
Like you have pubkey_hash, pubkey, script_hash, ..., "embed_hash"

Maybe just a script with a single 20 byte push data.

Advantages:

* Optimisation possibilities (you know this can't be spent, and the script can't be processed).
* Avoid indexing in an address database Bitcoin addresses which are currently being
used to index data. They will never be spent, yet they will be indexed because they look
identical to normal Bitcoin addresses.

By separating this class of Bitcoin usage, we can improve the core Bitcoin payments system.