Another possibility would be to embed a text message in the transaction. There's no provision in the GUI for it, but the source code allows for it (it's just not implemented at the moment).
I did not know that you can send messages with your transactions.
As Gavin said, you can't. But I didn't say you could - I said the source code supports it. Subtle but important distinction. It would require modifications to pass messages in the prerequisite script passed to SignSignature. And, of course, modifications to see what's there.
I already understood that with the current bitcoind client you can't send messages with your transactions because otherwise people would be using it but what it sounds like you're saying is that someone could create a patch for the bitcoin sourcecode which would add this functionality to bitcoin even though there are no plans from the developers to include a messaging feature. In the case where Gaven modified the source to include a vanity feature, someone else in the next half hour could modify the source to allow a PGP public signature to pass with the transaction and then anyone with that modified source would be able to see it or the intended recipient would also be able to see the PGP public key. And finally; this could be done without disrupting the Bitcoin network because you're using something that's already in the protocol?