There are two types of multisig outputs available at the moment that are useful for us.
While technically I can think of no reason to not support any 1-out-of-n transactions, the reference client won't relay or mine these for now. It also seems then if you use uncompressed public keys they are not valid ECDSA points which means that we are stuck with compress public keys for now until somebody finds a way to use uncompressed ones.
What this means is that we can use a maximum of 128 bytes per multisig-output (two compressed public keys of 64 bytes each). Since the first public key will always be one of our own public keys so we can redeem the output.Grazcoin suggested we could use the public key to encode the Bitcoin address of the receiver. However I think this might be more trouble then it's worth. If you convert a Bitcoin address to a hex string you would end up with a 68 byte string. Which is just over the length of one public key. It would make parsing the much harder since you are guaranteed to need two ouputs for every transaction.
I would like to suggest that we keep the original spec and use one output for the receiving address. We also need to rethink the sequence number. Since we always know what the target address is we no longer have to use a sequence number based on the receiving address and since public keys are kept in order in a multisig output (although I would appreciate if somebody could confirm this) we don't need sequences on a per public key basis, we need them per output.
We can just use a integer that counts up from zero, per multisig output, making sequencing much easier in the new situation.A simple encoded simple send would look like (and forgive my horrible photoshop skills):
https://dl.dropboxusercontent.com/u/374/SimpleSend.pngA complete tx could look something like this:
{"hash":"c4551b2e0b8470cc3e03212f823cb9a66580c512aa66ac71a4bfc0a6500dd1eb","ver":1,"vin_sz":1,"vout_sz":2,"lock_time":0,"size":305,
"in":[{"prev_out":{"hash":"c9fc3f6f8dc828d11eab3196393f13e8c147f835d2d0568df26009aba9617a6e","n":0},"scriptSig":"3046022100cb314569b0b194c2e510a101c5a6d9ec5a95a9a8cfc4009bd8f11affbec1b835022100b6e8b08be3b42e037a18f497a595996c40c49e83b114dc360601fdb3526e4d8001 04ea5fbd95738d81e3857067e8156b0887aad60ba2018c21807705c0e5cd4ee9f5187d56e6a827b5c7f54721c46c9c372bdc929a16f3331c3290fdbebc55a7572e"}],
"out":[
{"value":"0.00006000","scriptPubKey":"OP_DUP OP_HASH160 e8c6391242865cb288487d938f87d40706381c12 OP_EQUALVERIFY OP_CHECKSIG"},
{"value":"0.00006000","scriptPubKey":"OP_DUP OP_HASH160 exodusaddressshouldbeinsertedhere OP_EQUALVERIFY OP_CHECKSIG"},
{"value":"0.00006000","scriptPubKey":"1 02c5ac10feed00d99b6571bb42567d43e255b8ace9adf078908e3c4827f954d918 020000000001000000020000000000000001000000000000000000000000000000 2 OP_CHECKMULTISIG"}]}
I appreciate some feedback on this spec before I start writing code

Wow, it's becoming harder and harder to stay up to date with Mastercoin.
First off, Tachikoma thank you for all your work. You've contributed far more than anyone else to Mastercoin. I'm sad to hear you are demotivated by the way some community members react.
Back to the new data method proposal: I can't see any error in the details of what you said. That transaction does contain the data, and the bitcoins are redeemable via the actual public key. Nevertheless, the mysterious PM dacoinminister cited got me thinking more broadly about the method. I think there might be a more general problem in the concept of storing data in the blockchain using multisig txs. For mastercoin to work we need mastercoin transactions to be stored in a decentralized, permanent way (like bitcoin transactions are). Using multisig transactions and then taking the bitcoin away with the other key may cause the transaction to be pruned from the blockchain by future bitcoin clients (why would you need to store transactions which have all its outputs spent?). In fact, the same should happen with ANY method which doesn't bloat the UTXO. If a transaction can be pruned for whatever reason (multisig, op_return), it means bitcoin clients could potentially delete that transaction, thus deleting mastercoin data?
Clearly my technical knowledge of the bitcoin protocol is below most of the people reading/writing here, so I'm sorry if what I'm saying is stupid.