Currently the most efficient solution I've found that will work with any SOQL query through the partner API is to persist the sObjects returned from the initial QueryResult and the query locator incase a page is requested outside the current results.
This required a level of paging support on top of the Salesforce QueryResult.
I.e. When a page is requested sObjects may be required from:
- The current (cached) QueryResult
- A subsequent QueryResult that can be fetched using the query locator
- A prior QueryResult
- Some combination of all three.
If the page spans two (or more) QueryResults an artifical QueryResult will need to be created with all the required records.