Somewhere lost in the mists of time (HPRM 8.1.x or so) there was an issue in the HPRM web client which caused the second page of your search results to sometimes contain results that you had already seen in the first page. We fixed this in a patch of course.
Upgrading to the latest patch is not always achievable, maybe, just maybe there is a work-around? Turns out there is, try putting this inside the routeDefaults element of your hprmServiceAPI.config file:
<add name="Record" model="Records" sortBy="recRegisteredOn- unkUri" includePropertyDefs="true" />
What is going on here? The sort by Uri puts the search results in a predictable and static sequence, the sort by date registered puts them in a useful sequence.
Not only a work-around
Given that the Web Client does not yet support custom sorting you may wish to use this technique to sort search results by something more meaningful than the default.