La implementación con POST es correcta, porque la primera vez el usuario manda el filtro por el formulario. A partir de allí, para que el paginador mantenga el filtro de una página a la otra, hay que pasarle de alguna manera esta información de filtro. Por tanto, cuando el usuario hace click en el formulario, se mandan las variables POST, haces la consulta Y generas los links de anterior y siguiente con el parámetro indicado. Al pulsar siguiente, el programa busca el filtro, si está en post lo aplica, si no, lo busca en get.
http://www.desarrolloweb.com/articulos/1035.php
Saludos