He borrado todas las fotos de mi iPhone 4, pero el uso del teléfono e iTunes siguen mostrando 16gb de fotos.

La mejor manera de atacar esto es hacer una buena copia de seguridad (tal vez dos - una a iTunes y otra a iCloud) y luego restaurar el dispositivo.

Cuando actives el teléfono, no inicies sesión en iCloud (o en la tienda de aplicaciones), simplemente configúralo como un nuevo dispositivo. Desde allí puedes mirar el almacenamiento y luego agregar lentamente tus cuentas de Apple.

Cuando te conectes a iCloud, mira el almacenamiento y mira si está descargando fotos de la unidad iCloud, los archivos de mensajes, el flujo de fotos, etc...

Mi sospecha es que tienes iCloud y las "fotos" son de los datos que bajan del servidor - incluso sin tener fotos en la aplicación de fotos / rollo de cámara.

Una vez que tengas una buena idea de qué elemento está causando que las "fotos" lleguen, puedes borrar el teléfono y configurarlo desde tu copia de seguridad si lo deseas. También puedes reinstalar las cosas que quieras en el dispositivo que estaba "configurado como nuevo" si eso es más fácil que restaurar una copia de seguridad y borrar las cosas que no quieres.