This online demo does exactly what you want. Make sure that you wire the controls like in the demo in order to do both the sorting and the paging on the server like shown in this example. You can see what queries are being sent to the server as demonstrated in the online example or with a tool such as Fiddler or Firebug or SQL Server Profiler.
When you sort the grid and have paging you should be seeing something like this:
--> Requesting http://services.odata.org/Northwind/Northwind.svc/Customers()?$orderby=ContactName&$skip=10&$top=10&$inlinecount=allpages
The yellow stuff is the sorting which happens before paging (the orange stuff).
By the way, the RadDataServicesDataSource does nothing magical or special. It simply build this OData query and sends it to the server. If the server returns "wrong" data then there is nothing we can do about that.
I hope this helps.
the Telerik team
Explore the entire Telerik portfolio by downloading the Ultimate Collection trial package. Get it now >>