Ok, estoy rehaciendo mi respuesta porque estoy bastante seguro de que he descubierto todo lo que está ocurriendo aquí 
Como menciona @ninjapenguin, si tienes una etiqueta y eliminas todos los temas a los que se le ha aplicado esa etiqueta, la etiqueta sigue apareciendo en la página de etiquetas y el contador no cambia. Creo que esto sucede porque los temas todavía técnicamente existen y siguen manteniendo la etiqueta.
@syl, si navegas a la lista de temas de la etiqueta tete como se muestra en tu captura de pantalla y luego agregas
?status=deleted
al final de la URL, deberías ver dos temas eliminados listados con la etiqueta tete.
El mensaje informativo en tu segunda captura de pantalla corresponde al número de temas eliminados que tienen la etiqueta aplicada.
Siento que probablemente no deberíamos tener en cuenta los temas eliminados al contar/listar etiquetas, pero esto podría no ser un cambio super trivial dado cómo se almacena todo en la base de datos. ¿Qué opinas @codinghorror?