Paginação + pesquisa = problema

Gente to com um problema que meio que não estou conseguindo pensar em uma solução, tenho uma página que apresenta os dados para os usuário nesta página tenho.

1- Botão para cadastrar novos usuários - Que passa a ação via um get e chama a página para cadastro usuário.

2 - Logo abaixo existe os campos para pesquisa de usuário - Que passa os dados via post para a url.

3- E finalmente - a listagem dos usuários cadastrados, paginada - Que atualmente passa os dados via get pra url.

O problema é quando a pesquisa funciona perfeitamente a paginação não funciona direito e quando a paginação funciona ai é pesquisa que não funciona.

Existe uma solução que chega o mais perto de um funcionamento adequado a solução é:

Quando eu passos os atributos da pesquisa via post, se por exemplo a pesquisa me lista duas páginas com a solução ao clicar no link para ir para a segunda página os post's são todos descetados e pesquisa é desfeita. Exceto por esse ponto deixar dessa forma funciona quase de modo perfeito.

Soluções que já tentei:

1- Botar tudo via "get", só que como estou usando formulários diferentes ao mudar a página acabo perdendo os dados que estão na url do outro formulário.

2- Inverter e passar a paginação via post e a pesquisa via get(mesmo que essa solução funciona-se acho que só a usaria em ultimo caso, já que os parâmetros para pesquisa poluem a url). Só que o problema é que o número das páginas são links, ai não da para mandar algo via post já que os links sempre vão para a url.

3- Estou pensando em usar controle de sessão para isso, mas ainda não conseguir pensar em como aplicar talvez seja só loucura da minha cabeça. mas não estou conseguindo ver outra solução.

E ai alguém tem alguma sugestão para eu resolver este problema?