I think transaction fees are the only appropriate course of action for situations where information is to be stored forever.

That storage has a cost, and the person using it should bear the cost.

On steem, for example, transactions aren't free. Nothing in life is free.

On steem, transactions are subsidized by the witnesses-- not free.

"Free transactions" basically violates the laws of physics in an immutable context -- they will eventually cause the system that hosts them to come crashing down under its own weight.