Deberías exponer el modelo de datos que trabajas .. sobre todo cuando haces mención a que tiene muchos "detallitos" sobre el diseño de esta ..
Así te aconsejaran la mejor consulta SQL para tal fin .. una vez tengas tus datos (todos) obtenidos .. ahí podrías usar scripts de paginado genéricos como:
Paginator (de Jpinedo)
http://jpinedo.webcindario.com/scripts/paginator/
Para un sistema de paginado como el que te comento .. lo "único" que tienes que tener claro es tu sentencia SQL que te tome los registros de las N tablas implicadas a base de las relaciones entre ellas. Si bien los ejemplos suelen aplicarse por "sencillez" a una sóla tabla .. te puedo asegurar que si tu compones tu sentencia SQL compleja (donde intervengan N tablas relacionadas) y obtienes tu resultado (total) esperado .. usar scripts como "Paginator" este ya se encarga de añadir a tu sentencia SQL el "LIMIT" como corresponda y gestionar la generación de los links para el paginado.
Un saludo,