Really confusing and cumbersome

[eluser]PhilTem[/eluser]
I think it's best practice. Or at least most commonly used.

Or you'll add the search query as a get-parameter to your pagination links and your search-logic will first look for a post parameter, if none is found look for get parameter, if none is found display the pure search form.