As far as I can see you are using the 2009.1.526 version of our controls and I would like to suggest an upgrade to our latest Q2 2009 SP1 release. With Q2 we introduced our new data engine wich is faster and more capable than the previous one - implementing some sort of paging a is alot harder with previous releases.
There is an example in our QuickStart application that demonstrates server-side paging, filtering, and grouping. Unfortunately the example is only available offline. Once you start the Q2 demos that come with our installation you can find the paging example under GridView -> Performance -> Server page, sort, etc.
Hope this helps.
the Telerik team