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):

A 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
