Ran into this problem and searched high and low for a solution but never found another post detailing the solution.

The issue is that, according to the documentation for GetListItem, located here:

http://msdn.microsoft.com/en-us/library/lists.lists.getlistitems.aspx

Paging should be  done like this:

The GetListItems method supports server-side paging. The XML data returned by this method includes a ListItemCollectionPositionNext attribute inside the rs:Data element that contains the information to support paging. This string contains data for the fields in the sort and for other items needed for paging. You should consider this string internal and not to be modified; modifying it can produce unexpected results. The following example shows the form of this return value when paging is supported.

Xml
<rs:Data ListItemCollectionPositionNext=" 
Paged=TRUE&p_ID=100&View=
      %7bC68F4A6A%2d9AFD%2d406C%2dB624%2d2CF8D729901E%7d&PageFirstRow=
      101" Count=1000 >
   <z:row ows_FirstName="Nancy" ows_LastName="Name" ….. />
   ...
</rs:Data>

To get the next page of data, the queryOption parameter is used, as shown in the following example.

Xml
<QueryOptions>
  <Paging ListItemCollectionPositionNext=" 
    Paged=TRUE&p_ID=100&View=
    %7bC68F4A6A%2d9AFD%2d406C%2dB624%2d2CF8D729901E%7d&PageFirstRow=
   101" />
</QueryOptions>
 
The issue with the above documentation is that when you try to load the above into an XmlElement, then it will fail because the attribute has invalid characters in it.  You can try escaping those characters, however then Sharepoint will not recognize it as a valid pagination token and you wont get proper pagination.
 
 

The trick is to build the XML string with that information blank like this:

 

<QueryOptions>

  <Paging ListItemCollectionPositionNext=”” />

</QueryOptions>

 

Then load it into the XmlElement using the InnerXML, as before.

 

optionsQuery.InnerXml = queryOptions;

 

The go directly to the attributes innertext and set the value:

optionsQuery.ChildNodes[0].Attributes["ListItemCollectionPositionNext"].InnerText = "Paged=TRUE&p_ID=100&View=
    %7bC68F4A6A%2d9AFD%2d406C%2dB624%2d2CF8D729901E%7d&PageFirstRow=101";