Оберните "Новое!" в пролете внутри якоря:
<a class="newText" href="somepage.html"><span>New! </span>Watch video</a>
и в вашем CSS установите:
a.newText:visited span { display: none; }
Я бы порекомендовал использовать класс на привязке (например, «newText» выше), чтобы это форматирование применялось только к тем ссылкам, на которые вы хотите. И имейте ввиду, что «Новый!» текст снова появится, если пользователь очистит историю своего браузера.