Counterparty was originally designed to use the OP_RETURN output to store all of its message data, which I feel is very elegant, and leaves a minimal impact on the blockchain.
Message data does not belong in the blockchain,
only financial transactions.
This deserves further explanation without the meme.
Every Counterparty message is a financial transaction. From Wikipedia
http://en.wikipedia.org/wiki/Financial_transaction:
A financial transaction is an agreement, communication, or movement carried out between a buyer and a seller to exchange an asset for payment.
If it is unclear that any of the messages in Counterparty does not constitute a financial transaction, I would be happy to explain.
The message that may be the most vague is the "broadcast" so I will explain it here. The "broadcast" is a communication of pricing information from a tertiary party that is used for resolution of bets and CFDs in Counterparty.
Pricing information that is recorded in an immutable ledger is essential. During the global financial crisis, the regulatory agencies called up every counter party to Lehman Brothers. Every trade with Lehman Brothers had to be revealed and the market data used to price the deal was required to reconstruct the pricing of the trade.