I see a problem: protocol only works for a client which scans whole blockchain.
Secure thin clients (similar to SPV clients like Electrum, MultiBit) are fundamentally impossible.
And running full node client like Bitcoin-Qt will soon be very challenging,
Hey Alex. I think think if this is successful then it will be possible to make thin clients. For instance, the code scanning the block chain doesn't need to run in the same place as the code signing the transactions.
Well, yes... You'll need it to run on servers you can trust. Otherwise server can make it look like you received a payment when you didn't.
Going further, I really don't see why you would want to bloat Bitcoin blockchain with data... Basically, you just need to timestamp messages, and there is much less wasteful way to do it.
E.g. you can put all these data-transactions into a Merkle tree and timestamp only root of that Merkle tree. Or you can use a merged-mined alt-chain.
Let's summarize You use Bitcoin for two things: secure timestamp via proof-of-work, and storage of data. Storage of data is expensive.
Thus you can drastically reduce costs if you store data elsewhere.