consider also that it’s possible to encode data into the bitcoin blockchain already, merely by specially crafting the transaction. (See the ‘first’ option on http://privwiki.dreamhosters.com/wiki/Bitcoin_DNS_System_Proposal#Overcoming_potential_resistance_bitcoin_developers.2Fcommunity ).
alternatively, only timestamping and proof of expense (i.e., a regular transaction with a fee) may be used, pushing off the actual data storage off to external service (see ‘third’ option, ibid.)
but why not make it easier on everyone and just allow say, 64 or 128 bytes of random data in a transaction? it seems that in the net, these side-band uses of bitcoin will only serve to increase the security of the network, by increasing the mining incentive, and bringing on more generation power.