Use sua primeira sugestão. Aquele com compensações. É a maneira "padrão" de fazer paginação. Colocar todo o conjunto de resultados em sessão seria uma má ideia, já que cada usuário teria sua própria cópia privada dos dados. Se você encontrar problemas de desempenho, sempre poderá adicionar cache (memcache) que beneficiará todos os usuários que acessam os dados.

O MySQL sempre resultará em seus dados da mesma maneira. A única maneira de um registro da página 1 aparecer na página 2 é se um novo registro foi inserido entre o momento em que o usuário navega da página 1 para a página 2. Em outras palavras:você não precisa se preocupar.

Um recurso no caso do MySQL é um tipo de ponteiro que aponta para o conjunto de resultados. Você pode então manipular isso (buscando dados linha por linha, contando o número de linhas retornadas etc). Não é mundial.