If your PHP file is named "file.php" and it is delivering the XML to feed the gallery, with a querystring parameter that indicates the sort order - the URL should be something like:
file.php?sortorder=random
If you request the same file again, because the parameter is the same, the server or browser may cache the content - which is great for performance, but defeats the script. To compensate, you can either send a random string (the time works well), so that each request has a different URL -
file.php?sortorder=random&t=32423
Or you could use the cache control headers at the very top of the file:
Posting more code may be helpful. You can use view source to display the output of the PHP code, and the XML as well.