You can much more easily publish data via the blockchain w/o OP_RETURN, and furthermore, you can easily put that data in to the UTXO set which all nodes *must* have if they are to maintain consensus.
Mike Hearn suggested we adopt blacklists to solve this problem back when someone put the child porn sections of the hidden wiki into the UTXO set; no-one's come up with a better solution since. You can make publishing that data more expensive by a small linear factor - about 10x to 100x - but that's the best you can do.
The best solution to this problem is legal and political: the idea that you have to prevent every last trace of "illegal data" from getting into a public ledger is absurd.
All due respect Peter, but being concerned about having illegal data in a system is not absurd and in my opinion it is better to address this issue, because law enforcement certainly will in one way or other. Law enforcement agencies track down and close systems that promote criminal content such as child pornography and I would think that law enforcement will not handle Bitcoin differently when push comes to shove.