Olá bom dia.
Eu participei de uma palestra de especialistas da Microsoft em programação e disseram o seguinte:
1 - Ninguém pagina um grid de mais de 10 paginas
Imagina que seu grid tem um numero de linhas por pagina de 50 registros
então você deveria trazer 500 registros pra tela. TOP 500 na ordem que vc desejar.
2 - Na tela você deveria ter um TEXTBOX de filtro por NOME por exemplo
Imaginando que no item 1 acima, voce trouxe 500 primeiros nomes em ordem alfa, voce traria os nomes inciados por A, iniciados por B e etc.
se o usuários informar o filtro "RAIMUNDO"
Vc traria os primeiros 500 nomes contendo RAIMUNDO, ou o numero de registros que tiver;
3 - Isso deve ficar transparente para o usuário,
ou seja, informe ao usuario que trouxe os 500 primeiros registros e peça para informar o filtro se desejar outros registros.
Porque os especialista indicaram isso, segundo eles?
O usuário não vai pagina 5.000 paginas procurando algo.
e não faz muito sentido carregar tudo de uma vez, afinal tempo é dinheiro.
Espero que te ajude. Eu tenho feito isso.