The only reason Starfleet found out in "Redemption" is because of Sela. There's no evidence that Sela did not exist before YE. At first, the 'new' uniform (the one with the collar) was only used for senior officers. Junior officers continued to wear the one without the collar. Eventually this was phased out completely.