Vorläufige Lösung:
Nachdem ich nun 2 Tage lang alles mögliche probiert habe, habe ich einfach noch einmal genau die gleichen Ordner direkt auf dem MailServer erstellt und dann in Thunderbird gelöscht.
Dies war tatsächlich ohne weitere Schwierigkeiten möglich. Ich gehe deshalb davon aus, dass es sich tatsächlich nur um ein Cache Problem gehandelt hat. Verwundert mich aber eigentlich schon etwas, da es bei einigen Ordnern beim ersten Mal sofort funktioniert hat und bei 2 nicht.
Ich habe jetzt mal 1 Ordner aufgehoben, fals noch andere Lösungsvorschläge gemacht werden, kann ich die dann gerne testen.