Ya vi donde puede estar el problema. Te explico brevemente, cuando haces la paginacion lo que indicas es que los resultados de una consulta los vas a dividir en grupos de un numero determinado de registros y de esa forma tienes página 1, página 2, etc. Sin embargo cuando vuelves a llamar la página buscar.asp, con los indices de las páginas siguientes, no estas enviando la palabra de busqueda, unicamente estas enviando el numero de página, pero para el ASP es como si la llamaras de nuevo y en el buscador una palabra vacia, por eso te envia todos los resultados.
Lo que debes de hacer es ademas de enviar la página, también tienes que enviar la palabra que el usuario proporciono en el buscador. de esa forma se vuelve a generar la misma consulta y ahora si puedes acceder a la página que estes requiriendo.
Entra a este sitio:
www.mundovid.com
En el buscador pon alguna palabra de un comic y luego ve a la parte final de la página en donde estan las páginas y pon el mouse encima de uno de los numero, veras como se envia el numero de página y el texto que pusiste en el buscador.
Espero te sirva
Saludos