A sua paginação está sendo perdida porque no momento da paginação você está carregando os dados e eles estão vindo na ordem original...nesse caso você precisa usar os dados já ordenados.
1. Guarde o resultado da sua pesquisa na session.
2. No Sort busque o resultado na session e ordene conforme você precisa. Depois salve novamente na session o resultado.
3. na paginação você só precisa mudar o pageindex, setar o datasource com dados da session e dar databind.
Teste dessa forma e poste aqui o resultado ;)
Abraços !
Diego Murakami MCP, MS - http://about.me/dii
* Por favor "Marcar como Resposta" caso esta for útil para sua dúvida.