An element of time-travel, parallel universe, and temporal-anomaly stories, the object and persons at the center of a paradox-event tends to survive and remember the event. As I was reminded by Darael the Paradox Machine was turned on after the Valiant was created, so even if the timeline was undone, it would only revert to a time after the Valiant was built.
Though the Master claims to have built the Valiant entirely, it is likely part of its design came from UNIT. The Master used a technology called a Paradox Machine, a part of a stolen TARDIS, to allow paradoxes to exist. When the machine is destroyed by Jack Harkness, the paradox destabilized and reverted to the previous unaltered universe.
In this case, the Valiant was at the center of the storm and even though it was part of a timeline that no longer existed, created at facilities which may no longer exist, its presence persisted in the new restructured timeline.
In the following year in an erased timeline, the Valiant was the base of operations for the Master. The Jones family (with the exceptions of Martha, who had escaped, and Leo) and Captain Jack Harkness were imprisoned on the ship, as was the Tenth Doctor. It also held the paradox machine inside the Doctor's TARDIS. When the timeline was erased, the Valiant was the only point in space and time not to revert, instead moving directly through time, due to it being the "eye of the storm", that is, of the paradox machine. (TV: Last of the Time Lords)