I someways making the transaction un-prunable is better for messaging, but I understand your concern.
One way to do it could be to use an M-Of-N 1 of 2 multi-signature transaction and have the 2nd public key as the message. The tx would then still be spendable with the first public key, but not many clients would be able to redeem it. I'm open to suggestions?
Embedding messages is really abuse of the (main) blockchain, which is for currency transactions. The correct way to do this is to setup some merged-mined data that ties the message to the transaction id, and distribute the message as