Mi sembra strano che sia un problema di cache, se le immagini si chiamano tutte in maniera diversa. Sarebbe un problema se generassi dinamicamente le immagini, ma dallo script non sembra.
Allo stesso tempo mi sembra strano che il problema sia dovuto all'inizializzazione di rand() con srand(), perchè dalla versione 4.2 in poi dovrebbe farlo in automatico.
Il codice html generato per il menu è sempre lo stesso? Oppure effettivamente lo script richiama immagini casuali?