I am not sure short paid messages would really bloat the blockchain. Just few additional hundreds bytes per transaction with increased fees. Though it is correct: miners are not the only ones who carry costs. Probably full nodes could prune old messages or messages that are not addressed to them (just to save some disk space).

Update: though probably you are right, it would cause problems (not only blockchain size, but also copyright infringements, propaganda  of racism and other extreme cases of freedom of speech)... Probably better to have messages separate, maybe to integrate with IRC (AFAIK bitcoind had some code to deal with IRC already).