Das Verhalten ist nicht komisch. Es gibt für das dahinterstehende Problem nur zwei mir bekannte Lösungsansätze: Entweder die „saubere“ SEO-URL bekommt einen eindeutigen Identifikator (wie die Kategorie-ID) oder man führt eine Liste mit allen aktuellen und vorhergehenden SEO-URLs, um die Zuordnung zu gewährleisten.
Es ging theoretisch auch ohne Historisierung. Das halte ich aber nicht für ein tragfähiges Standard-Verhalten.
Und warum soll eine kryptische URL besser für mein SEO sein, als eine saubere 301 Weiterleitung?
Da verwechselst Du jetzt etwas. Die 301-Weiterleitung funktioniert sauber – von der alten SEO-URL auf die neue. Du versuchst aber offensichtlich eine neue Kategorie mit einer SEO-URL auszustatten, die schon mal vergeben war. Die SEO-URL der neuen Kategorie kann also nicht erstellt bzw. zugeordnet werden. Daher dann die in jedem Fall eindeutige, technische URL.
Das mit dem Löschen (oder ggf. auch Umschreiben) weiß ich ganz sicher. Allerdings sollte man wissen, was man tut. Immerhin ist das ein direkter Eingriff in die Datenbank. Im Zweifel also bitte ein Backup anlegen.