Usa tu primera sugerencia. El que tiene compensaciones. Es la forma "estándar" de hacer la paginación. Poner todo el conjunto de resultados en sesión sería una mala idea, ya que cada usuario tendría su propia copia privada de los datos. Si tiene problemas de rendimiento, siempre puede agregar el almacenamiento en caché (memcache), lo que beneficiará a todos los usuarios que acceden a los datos.
MySQL siempre dará como resultado sus datos de la misma manera. La única manera de que un registro de la página 1 aparezca en la página 2 es si se inserta un nuevo registro entre el momento en que el usuario navega de la página 1 a la página 2. En otras palabras:no tiene de qué preocuparse.
Un recurso en el caso de MySQL es una especie de puntero que apunta al conjunto de resultados. Luego puede manipular eso (obteniendo datos fila por fila, contando la cantidad de filas devueltas, etc.). No es global.
