The fix is in deciding when the change takes effect, and only validating with the stricter rule from that point onwards.
The easiest way is to decide upon a block height, say: 695,837 and all the blocks before that one are validated with the old rules, and blocks 695,837 and onward are validated with stricter rules.
Something a bit more sophisticated was used for SegWit. Every 2016 blocks, the difficulty gets modified to make sure we get a block once per 10m on average. These 2016 block intervals were used to gage support for the softfork, through signalling in the version bits of each block. Miners get to set these when they find a block, and only when 95%+ of the blocks in a 2016 timespan contained a certain flag would SegWit activate. This way, there was no fixed block height dictated in code, but instead, the miners together were able to dictate the lock in of the soft fork.