It's tempting to see this kind of abuse through the lens of fees, because we only have a few hammers and so everything looks like a kind of nail. The problem is the moment you try to define "abuse" economically you end up excluding legitimate and beneficial uses as well. Maybe Peters patch for uneconomical outputs is different because of how it works. But mostly it's true. In this case, fees would never work - Peter said the guy who uploaded Wikileaks paid something like $500 to do it. I guess by now it's more like $600-$700. It's hard for regular end users to compete with that kind of wild-eyed dedication to "the cause".

The root problem here is people believe the block chain is a data structure that will live forever and be served by everyone for free, in perpetuity, and is thus the perfect place for "uncensorable" stuff. That's a reasonable assumption given how Bitcoin works today. But there's no reason it will be true in the long run (I know this can be an unpopular viewpoint).

Firstly, legal issues - I think it's very unlikely any sane court would care about illegal stuff in the block chain given you need special tools to extract it (mens rea). Besides, I guess most end users will end up on SPV clients as they mature. So these users already don't have a copy of the entire block chain. I don't worry too much about this.

Secondly, the need to host blocks forever. In future, many (most?) full nodes will be pruning, and won't actually store old blocks at all. They'll just have the utxo database, some undo blocks and some number of old blocks for serving, probably whatever fits in the amount of disk space the user is willing to allocate. But very old blocks will have been deleted. 

This leads to the question of what incentives people have to not prune. The obvious incentive is money - charge for access to older parts of the chain. The fewer people that host it, the more you can charge. In the worst case scenario where, you know, only 10 different organizations store a copy of the chain, it might mean that bootstrapping a new node in a trust-less manner is expensive. But I really doubt it'd ever get so few. Serving large static datasets just isn't that expensive. Also, you don't actually need to replay from the genesis block to bring up a new code, you can copy the UTXO database from somewhere else. By comparing the databases of lots of different nodes together, the chances of you being in a matrix-like sybil world can be reduced to "beyond reasonable doubt". Maybe nodes would charge for copies of their database too, but ideally there are lots of nodes and so the charge for that should be so close to zero as makes no odds - you can trivially undercut someone by buying access to the dataset and then reselling it for a bit less, so the price should converge on the actual cost of providing the service. Which will be very cheap.

There was one last thought I had, which is that if there's a shorter team need to discourage this kind of thing we can use a network/bandwith related hack by changing the protocol. Nodes can serve up blocks encrypted under a random key. You only get the key when you finish the download. A blacklist can apply to Bloom filtering such that transactions which are known to be "abusive" require you to fully download the block rather than select the transactions with a filter. This means that people can still access the data in the chain, but the older it gets the slower and more bandwidth intensive it becomes. Stuffing Wikileaks into the chain sounds good when a 20 line Python script can extract it "instantly". If someone who wants the files has to download gigabytes of padding around it first, suddenly hosting it on a Tor hidden service becomes more attractive.