Let's have some figures, shall we?
Tarsnap charges 300 picodollars / byte-month. Assume ten thousand full nodes with their own blockchain, that's 3 microdollars / byte-month, or 3*12*80 microdollars / year = 0.3 cents / year for 80 bytes. But of course the cost of storage falls exponentially, let's say a three year halving time; then the total lifetime cost for storing your 80 byte OP_RETURN on every full node in the Bitcoin network is given by the sum of a geometric series with first term 0.3 cents and common ratio 2^(-1/3).
That's a total cost of 1.5 cents. At current prices, and with the above generous assumptions made on behalf of miners and other full node operators, the
correct maximum additional charge for a filled 80 byte OP_RETURN is 0.025 m
BTC (it can be argued that the additional demand for Bitcoin created by permitting new uses is a driver of increased Bitcoin prices and thus should lead to a discount, but that's harder to quantify). So just set that as the default until floating mining fees are introduced in (hopefully) 0.10. Bitcoin users who don't want to "provide" that storage can go ahead and not run a full node.
The idea Luke-Jr raises occasionally of a social contract existing between Bitcoin node operators to store and process only financial transactions needs dealing with. Bear in mind that in his maximalist interpretation, absolute consensus between all node operators is morally required to change that contract. It falls through on several grounds, principally vagueness and lack of historical support. Vagueness we've seen in this thread: no-one is quite clear on what makes a transaction financial. Is a transaction transferring a currency other than Bitcoin part of the social contract? Is a transaction containing what is effectively routing data (c.f. stealth addresses) fully financial, or is the additional stuff an anonymity functionality not part of the social contract? And so on. As to historical support, allow me
to quote from someone who would know:
The network is robust in its unstructured simplicity. Nodes work all at once with little coordination. They do not need to be identified, since messages are not routed to any particular place and only need to be delivered on a best effort basis. Nodes can leave and rejoin the network at will, accepting the proof-of-work chain as proof of what happened while they were gone. They vote with their CPU power, expressing their acceptance of valid blocks by working on extending them and rejecting invalid blocks by refusing to work on them. Any needed rules and incentives can be enforced with this consensus mechanism.
The thing is, Luke, that like it or not, Satoshi is/was a libertarian, and his creation embodied the 'take it or leave it' aspect of that political philosophy. Consensus means a consensus of mining power. Coordination means passing around proofs of work. If you feel that the amount of storage space the blockchain needs is too onerous to justify running your huge mining network, then by all means take your ball and go home, or for that matter start playing a different game - you have every right to reject whatever blocks you wish. Bitcoin will be just as pure as the majority of mining power wishes it to be.