Ok, ich formuliere meine Antwort noch einmal um, da ich ziemlich sicher bin, dass ich nun verstanden habe, was hier genau vor sich geht 
Wie @ninjapenguin bereits erwähnt hat: Wenn du ein Tag hast und alle Topics löschst, die dieses Tag verwenden, bleibt das Tag auf der Tags-Seite aufgelistet und die Anzahl bleibt unverändert. Ich vermute, dass dies daran liegt, dass die Topics weiterhin technisch existieren und das Tag somit noch immer gespeichert ist.
@syl, wenn du zur Topic-Liste des Tags tete navigierst, wie in deinem Screenshot gezeigt, und dann
?status=deleted
ans Ende der URL anfügst, solltest du zwei gelöschte Topics mit dem Tag tete sehen.
Die Informationsmeldung in deinem zweiten Screenshot entspricht der Anzahl der gelöschten Topics, die dieses Tag verwenden.
Ich habe das Gefühl, dass gelöschte Topics bei der Zählung und Auflistung von Tags eigentlich nicht berücksichtigt werden sollten. Dies könnte jedoch keine besonders einfache Änderung sein, da die Daten in der Datenbank so gespeichert sind. Was denkst du, @codinghorror?