If anyone was curious, we figured out a partial (if inelegant) solution to our own issue, and the problem only recurs rarely at this point.
I'm not sure which portions of our process are crucial, and which are merely voodoo. We created a new stripped-down Flex map, that includes all of the layers in the real map, but nothing else. The Flex is coded to pan to the left and zoom in every 30 seconds (hopefully forcing a refreshing of all the layers), until it reaches the maximum zoom.
Alternately every twenty minutes, we have a script open this map, as well as the aforementioned script (which calls the individual REST pages). At this point, all the layers tend to appear immediately (or within a second or two) upon opening the map viewer.
Joshua Muse