There are several "reasonable" modifications to the Bitcoin protocol that would make some methods of encoding messages break (e.g. pruning).
Are any of the existing encoding methods future proof, in the sense that they are likely to continue functioning even after "reasonable" changes to the Bitcoin protocol?
With pruning as envisioned today, only spent outputs are pruned. By making a small transaction and never spending it, you can keep the encoded data intact.
In the future it may be that unspent outputs will still be pruned if they're old and low-value, for example as suggested here, in which case you can still extend the life of your message by putting it in an unspent transaction with a high enough value.
If the encoding is in the receiving address itself, this will also resist modifications such as forced consolidation of outputs - but if you want to also be able to salvage the committed coins, the message should be short and the address should be generated with a vanity address generator.
Bitcoin headers are probably never going to be changed much, so you can try encoding messages there. You only have limited space in Merkle Root (with partial hashing collisions) and Nonce, so you won't be able to encode much there. You could try encoding something in the hash of the block, but that would make it very expensive (storing n bits would mean creating about 2^n blocks before a message would be encoded).
If you believe the coin generation transactions would not be pruned, you could try using them for encoding your messages, which would be quite cheap if you mine your own blocks, or have someone that would let you encode some messages in their blocks.
After that, there aren't that many places that could be safe from potential pruning. Then again, some people will probably be keeping the entire block chain, so message encoding in the traditional way might not ever go away...
