Welche System Versionen hast du auf den Geräten installiert? Synchronisieren alle Geräte mit iCloud Photos (Library)?
Sind iOS Geräte mit älteren Systemversionen dabei?
In früheren Versionen von iOS hatte ich auf meinem iPhone das Problem, dass das Löschen Dees "Zuletzt Gelöscht" Albums nicht geklappt hat, wenn es zu voll war. Seit dem bin ich vorsichtig und lasse es nicht voller werden als weniger als tausend Fotos in Zuletzt Gelöscht. ich musste alle Fotos aus Zuletzt Gelöscht entfernen und in kleinen Gruppen einzeln wieder löschen.
Auf welchem Gerät und mit welcher Systemversion versuchst du zu löschen?
Wenn alle deine Fotos in iCloud sind, könntest du versuchen, das Problem einzugrenzen, indem du vorübergehend nur einen Mac mit iCloud Fotos Mediathek synchronisieren lässt. Deaktiviere alle anderen Geräte für iCloud Fotos Mediathek und lösche die Fotos Mediathek auf diesen Geräten komplett (nicht für das Gerät mit der iCloud Fotos Mediathek. Damit solltest du sehen können, auf welchem Gerät sich die Fotos Mediathek nicht löschen lässt, falls es an einem einzigen Gerät liegt.
Dann versuche in der Mediathek, die mit iCloud synchronisiert, die Fotos zu löschen. Vielleicht klappt es dann ja, wenn du in kleinen Gruppen löschst und keine anderen Geräte die Synchronisation mit iCloud stören können.
Falls es immer noch nicht klappt, mache eine aktuelle Sicherheitskopie der Mediathek und repariere die Fotos Mediathek (Reparieren deiner Mediathek in der App „Fotos“ auf dem Mac - Apple Support). Eine Reparatur ist allerdings teuer, da danach die komplette Mediathek erneut in iCloud hochgeladen wird, um sie zu synchronisieren.
Falls die Fotos danach immer noch zurückkommen, würde ich Apple Support kontaktieren. Dann muss eventuell die Mediathek in iCloud auf Apples Servern repariert werden. Dazu benötigen wir die Hilfe von Apple Support.