Custom Paging in .net 2.0

Hi,

I need help in .net custom paging. The current asp.net application we have was not properly written, it takes all the results from a stored proc and displays those results in a session in the front end and then uses the huge session dataset to do the paging. The issue with this approach if the data and number of concurrent users also grow then the performance is badly hit and the page almost freezes.

So i am going to use custom paging, so i get only few records in the front end and perform custom paging but thinking of the current users and the increase in the data store on live production database, i am yet to device a approach on how i will managing the paging, meaning what happens if user clicks on some other custom page link and some new data at the point is entered into the database, which wont get displayed?
Do i work with static data at that point or do i take the dynamic data too?

we are using .net 2 framework.
Any thoughts or any direction would be highly appreciated.

Regards,
Rithesh