Yo tenía el mismo problema con el mismo código, que es de
www.aspfacil.com, y lo he solucionado poniendo antes de la apertura del objeto rs las siguientes lineas:
Set rs = Server.CreateObject("ADODB.Recordset")
rs.Pagesize=TamPagina
rs.CacheSize=TamPagina
rs.CursorLocation = 3 '''Creo que sobre todo esta es importante
rs.CacheSize=6
'Ejecuto la consulta
objrs.Open sql, Conexion, 1, 2
A mi me ha funcionado pq he usado el mismo ejemplo que puso en este foro pepelucho.
Espero que te funcione!!!!!
Si sigues teniendo el mismo problema, busca en aspfacil.com el artículo de paginacion de recordset, y dentro de esta seccion, los ejemplos.