I think what you're seeing here is snapshots of the same data that don't match because the data set is not being returned in a fixed order. The item set can be returned in different order on each call, so paginated results can vary. Pagination results are not drawn from a fixed set or order between page requests. In particular look at item 131662664002. It appears in your 2601_p1 and 2601_p2 results. This indicates that it changed position between calls. This can explain the other item changes as well. Default sortOrder is BestMatch. BestMatch is not your friend when you are trying to get a complete picture for >100 items. Since it is an undefined sort, the result order can't really be determined. Since you can only get slices, you can never be 100% that you got all items. Use a fixed sort. Be aware that StartTimeNewest has issues though:
"Since you can only get slices, you can never be 100% that you got all items." There is another way to approach this, but it is inefficient and the sort solution is better. You could repeat requests and store item data until the number of unique items stored matches the total count listed in the result set. This won't work when the item count is >100000, but it is potentially a way to retrieve more than 100,000 matches to query.