Is your document one continous story through linked frames, or does it consist of lots of disconnected "standalone" text frames?
Primarily, InDesign searches per story, in the order of creation. If you create a new textframe at the end of your document, then cut and paste it on the first page, it'll still be searched last.
"Per page" is not as straightforward as it may appear. On a single page, you may have text frames that continue a story from a previous page and/or continues elsewhere, and standalone text frames (possibly stacked on top of each other) -- but also, the phrase you are looking for may actually begin on one page and end on another.
(That said: when clicking "Find Next", a complicated GREP expression may appear to "skip" an occurrence it ought to have found, only to return to it later. I guess that happens because a GREP expression may be cut into individual sequences, and in a first run around, the first part gets searched, and when that is done, it continues with the second part.)
The document is about 240 pp. of both linked-frames, and stand alone frames. Generally, frames are not linked across pages.
Your second paragraph explains the behavior. Thank you!
A follow-up question: You indicate that InDesign is using order-of-creation for it's story-ID-sequence. Is there a (relatively fast) way to over-ride that, or assign stories new ID-numbers? I'm doing a lot of find-replacing that requires human evaluation of each "find", and it is nearly impossible (mid-process) to tell how far along the process is.