A solution which will work with SOQL query without bringing all the query results back through the partner API is to persist the sObjects which are returned from the initial QueryResult.
So, when a page is requested sObjects may be required from:
- A prior QueryResult
- The current or cached QuerResult
- A subsequent QueryResult which can be fetched using query locator
- Combination of three of these
If there are two or more QueryResults, an artificial QueryResult will be required to be created with all the needed records.