Paging using WCF service calls

See more:

WCF

SQL-Server-2008R2

I am working with WCF Services where we are exposing data as per client request. We have service which returns data for grid and this is where paging comes into picture. As of now We are using SQL 2008 which doesn't allow us to use fetch next.

So we are executing entire query every-time to return 10 rows. Is there any alternate solution so that for next call we can directly return data without executing query every-time.

My findings:

1. Use Caching: It may happen that caching may go down with large data and simultaneous calls from multiple user.

2. I can create new table where I will dump data from query with row number and with next call, I will return data from table. On first call we can return unique identifier which will be passed for next call to identify request. Personally I feel this bit complex and I don't think no one will agree on it.

Can you suggest some more ways ???