Just because you paid a fee to dump your waste doesn't mean it's not waste.

Yes, they paid the transaction fee to get put into a block, but now their data sits in the blockchain and eats up storage space on every device that maintains a copy of the chain. For a financial transaction you can at least comfort yourself with the knowledge that the "pollution" is an entry in a finance ledger, but not so here. The transaction fee is set based on how much people are willing to pay right now to get a transaction through, it doesn't factor in the long-term cost to store that transaction on every machine that needs to host it in the future... that cost is ignored.