Contracts on the blockchain point to
state roots in state storage which is additional to the blockchain data. The contract itself can never be deleted as it exists in some block. What can be deleted is the state data owned by the blockchain and this is encouraged by giving a gas refund on
However the majority of data may not be so simply accessed in order to be deleted. A
mapping (address => uint)) needs to have each of it's members deleted individually and can't be deleted all at once. The problem is that without additional storage and logic, mapping key's aren't stored and so the contract itself doesn't know at which addresses in the mapping data is actually stored at in order to delete it.
Clients like Parity and Geths 'fast' option implement state tree pruning which essentially ignores state data from dead contracts making the storage requirements considerably cheaper.