Con SQLServer 2005 se puede paginar directamente desde la base de datos, o sea, traerse solo los registros que se van a mostrar en cada página, en mi opinión esta sería la paginación más efectiva, puesto que las demás opciones, se traen todos los datos y luego se paginan, cosa que no evitaría, pues eso, el traerse todos los datos, cuando realmente solo queremos mostrar una reducida porción de éstos.
http://www.desarrolloweb.com/faq/pag...ql-server.html
Un saludo.