There are of course other issues to consider with regards to messaging, such as how to prevent spam (tx fees seem like the most obvious answer, but will people be willing to pay even trivial fees just to sign a transaction?).
This is the rub. You are either forcing lots of people who don't care about the data to receive it, or you are forcing lots of people who don't care about the data to receive it and those who do pay a tx fee. These are things better tackled outside of the primary network, imo.