Buenas,
puede ser que estés redireccionando con javascript, que en algunos casos genera esos problemas (digo en algunos casos, porque en ciertos proyectos me pasó, pero en otros, usando javascript, no me pasó...). Desde entonces, opté por redireccionar desde php. El código para hacerlo es muy simple:
Código PHP:
header("Location:la_url_de_destino.php");
El asunto es que estás escribiendo headers, o sea que para que funcione, no debe haber antes de esa línea ninguna salida -- nada de html ni espacios en blanco antes de abrir los tags de php (<?php o <?).
Si al seguir el enlace vas a un script distinto (el que hace las operaciones con los archivos) lo más probable es que se pueda adaptar fácilmente. Después de hacer todo el procedimiento, agregás el header de arriba para que redireccione y listo. No debería haber mayores inconvenientes.
Otra cosa que podrías probar sería pasarle un parámetro que siempre sea distinto al atributo "src" de los tags <img> (por ejemplo, un "timestamp", o sea, una referencia a la fecha actual en segundos). De esta manera, las imágenes no se quedarían "cacheadas" por el navegador, porque para el navegador siempre serían archivos distintos (el navegador "cachea" en base a una url completa; si cambian los parámetros, lo interpreta como un archivo distinto, no lo va a encontrar en el cache, y entonces va a pedirlo al servidor). Sería algo así:
Código PHP:
<?php
$fechaSegundos = time();
$strNoCache = "?nocache=$fechaSegundos";
?>
<img src="imagenTal.jpg<?= $strNoCache ?>">
<img src="imagenCual.jpg<?= $strNoCache ?>">
Dicho lo cual, te aclaro que no me parece lo más óptimo o recomendable (el caché existe por una buena razón, aunque a veces dé dolores de cabeza). Pero si lo demás no funciona, al menos será un parche, aunque va a aumentar la carga del servidor y va a hacer más lenta la navegación.
Otra observación: no conozco los detalles del script, pero en principio me parece una complicación innecesaria el renombrar las imágenes. Si tuvieras, pongamos, 100 imágenes, y eliminaras la primera, tendrías que renombrar 99 archivos, lo cual consume tiempo y recursos del servidor (y abre un flanco para que aparezcan errores difíciles de encontrar, sobre todo si el script no tiene un buen manejo de errores). No sé, en una de esas, hay una buena razón para usar ese método, pero a primera vista no me parece la mejor idea.
Suerte
Califa