Pagination loses some of it's luster with no knowledge of the total number of results. Is it possible to perform a "row count" with either REST or SOAP (getListItems) without getting back all of the items (eg: a request truncated with $top)?
Ideally you would request /_vti_bin/listData.svc/myList?$top=2 and get back 2 results and a count of the total. Is there any at all to accomplish this is SP2010?