Queridos amigos FOREROS, he encontrado una solución al problema de paginación, y os la muestro por si necesitais usarla algún día.
Navegando por la red y gracias a TARINGA y 'matiasl10' encontre esto:
http://jpinedo.webcindario.com/scripts/paginator/Paginator_v1.6.3.zip
Fuente: http://jpinedo.webcindario.com/scripts/paginator/index.html
Nota: Recomiendo que si haceís la entrada de la consulta dinámica, uses GET en lugar de POST.
Funciona perfecto.
Saludos ......