The Valiant doesn't revert to its (presumably not built) condition before the Master arrived in the 21st century because the paradox only started at and the rewind only went back to the point at which the 'Toclafane' came back to our time en masse. Everything else the Master did up until that point, up to and including designing Archangel and the Valiant, winning the election as Harold Saxon, and assassinating the President of the United States, still happened. Then he's shot by his wife, refuses to regenerate, and both the UK and US need new leaders.