Some immutable data structures can cope with missing data. Merkle trees are an example: to validate that a leaf is part of the tree, you don't need any of the other leafs (only their direct or indirect hashes). For the Bitcoin blockchain, it has been designed so that transactions where all outputs have been spent can be pruned, after the spending transactions have been validated. It wouldn't be hard to extend this to prune "illegal" transactions, even after they've been included in valid blocks; the only consequence would be that a node wouldn't be able to validate other transactions spending these "illegal" transactions (so it would have to risk accepting an invalid transaction, or rejecting a valid transaction, in both cases risking being on the wrong side of a fork).