Allow the value of the MaxRecordCount of a MapService to be set to -1 which means there is no record limit and all records that match a query will be returned to the requesting client.
At ArcGIS Server 10 there is a "Return ObjectIDs Only" query option that is not limited by the Max Record Count of the MapService. Then at 10.1 there will be a sortOrderFields parameter that hopefully will allow the IDs to come back in a sorted order. Using these two new options it should be possible to fetch records in pages where each page is less then the max record count and to be able to sort across all pages.
