Hola betoahm13!!
Antes de hacer cambios en la Fototeca yo esperaría unos días a que todas las fotos de iCloud se sincronicen en el iPhone. Quizás ahora se están sincronizando y al borrar fotos se satura un poco el sistema.
Si pasados unos días todo sigue igual, que al borrar una foto no se borra del todo, es posible que se deba a algún tipo de inconveniente de software. En ese caso, restaura el iPhone con iTunes en un ordenador.
Usa un cable original para conectar el dispositivo a iTunes.
Verifica que tienes actualizado tanto el ordenador que uses como iTunes y, si usas un PC, cierra todos los programas y desactiva el antivirus mientras trabajes con el dispositivo conectado. No te olvides de volverlo a activar una vez que acabes de gestionar el dispositivo.
Primero haz una copia de seguridad, para tener tus datos guardados: Cómo hacer una copia de seguridad del iPhone, iPad ... - Apple Support
En esta web de Apple tienes los detalles de cómo restaurar un dispositivo iOS: Restaurar tu iPhone, iPad o iPod a los ajustes de fábrica - Soporte técnico de Apple
Después le puedes restaurar la copia de seguridad, siguiendo los pasos de esta otra web oficial: Restaurar el iPhone, iPad o iPod touch desde una copia de seguridad ...
Prueba y nos cuentas.
Saludos!!