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.