I have solved the paging problems of ASP.NET and Microsoft Ajax, meaning
a) accessible links (regular href instead of linkbuttons)
b) ajax paging when possible (i.e javascript is available etc), still all pages are bookmarkable
The whole stuff is available as a free download ASP.NET Ajax paging solution - and packaged as "ASPCode.net.History"
I have also relased another free livrabrary for clientside cookie management - "ASPCode.net.cookie".
On my free games site I have both parts implemented - the paging as of now might not be all that user friendly - I turned to a semiautomatic solution where I set the url hash value to the hidden fields control name (control names are never beatiful in ASP.NET) along with the actual value - however it's easily modified to read something like "page-123" or whatever you are looking for.