SOQL Paging Data from the Database - Avoiding The 10,000 record limit

In some work I'm doing at the moment we're exposing quite a lot of data via web services and we were pretty confident that we'd never have to worry about any of the governor limits. However, the number of records grew and grew and eventually we slammed into the 10,000 row limit on a query. So how to get this data back? Using queryMore won't work since the calls in are unrelated, so some kind of "select everything from this point onwards" is needed along with a "limit x".

At first I thought why not just sort by id and then use where id > previous, but upon doing some research with the mighty google found out that you can't use the > and < operators with id fields. While reading about that I stumbled across a great work around (I forget where I read it, if I remember I'll link to it) - you can just create a formula field (of string type) on the object which takes the id as it's value. Voila, you can then use the > and < operators!

All that remains is to limit the query to some number, if the number of rows returned is the same as the limit then I make the assumption that there is more to come and return the id of the last record in the web service response. The client then knows to make another call, passes that id and I simply run the same query with where IDFormula__c > IDprevious. For the case where the call is made with no id, the empty string ('') comes first when using > so presents no issues.