This one is not intuitive. From within VSS Explorer, select the project, show history, check Labels Only, find the label of interest, click on Details, select the label text and delete it. Click Close, which will ask if you are sure you want to change the label. Click Yes and you’re done.