Introduce the following network rule:
 * a block is not valid if it contains a transaction whose hash
   already exists in the block chain, unless all that transaction's
   outputs were already spent before said block.

Warning: this is effectively a network rule change, with potential
risk for forking the block chain. Leaving this unfixed carries the
same risk however, for attackers that can cause a reorganisation
in part of the network.

Thanks to Russell O'Connor and Ben Reeves.