The protocol would need to be changed so a node can provide partial blocks. That's the point of the merkle tree structure, the pruning aspect was just never implemented.
In the case where an output both contains arbitrary data and is also spendable, you do indeed need to get >50% of the mining power to delete the transaction.
I think it'd be easy to make an analogy to a judge. If you publish a full page ad in the New York times containing some obfuscated or encrypted illegal material, that doesn't make the NYT, the printing company or people who bought the paper guilty of a crime. Now, the court of public opinion on the other hand ....