There's a simple way to do this without taking up space in the blockchain.
Simply send the transaction ID and your message to an external server, encrypt if desired.
This could be integrated with the client rather easily, but i'm wondering how many would actually use it - thoughts?
I doubt you'd get support from the official client unless the "external server" was actually a distributed network. Also, it should be encrypted with the public key the coins were sent to (the address). The recipient has the matching private key to decrypt it.
