Could we have an "extended memo" op that replaces the memo with text of arbitrary length?
We should have separate fields for encrypted ("public memo") and unencrypted ("private memo") contents, each of which can be arbitrary length (of course max tx size sets an effective limit). The client should automatically add a 64-bit nonce to the encrypted memo (and strip it on the receiving side). The nonce is to boost the entropy, e.g. if you're sending a bitcoin address in the memo field, without the nonce an attacker could find out the memo contents by simply encrypting all Bitcoin addresses in existence with the recipient's public key.
If the blockchain was frozen, I'd suggest re-purposing the burn op for this, but since we obviously have hardforks planned, it makes sense to just make a new op.