In den Rewriterules war ein kleiner Fehler bei den URLs zum Löschen von Beiträgen. Dadurch konnte es vorkommen, dass man beim Versuch einen Beitrag zu entfernen nur einen Fehler 404 bekommen hat.
Leider ist der Fehler zwar ziemlich oft aufgetreten, allerdings hat niemand das Problem gemeldet oder per PM darauf hingewiesen. Deshalb war er so lange im System bis ich selbst darüber gestolpert bin.
Naja, Hauptsache es passt nun wieder. Löschen sollte also wieder einwandfrei funktionieren.