Pues solamente cambia el método de tu formulario a que sea GET y al dibujar tus links de paginación pasando los parámetros, yo lo que hice es crear un helper para eso:
   
Código PHP:
Ver originalclass Admin_View_Helper_UrlParameters extends Zend_View_Helper_Abstract
{
    public function urlParameters($page)
    {
        $front = Zend_Controller_Front::getInstance();
        $request = $front->getRequest();
        
        $params = $request->getParams();
        $params['page'] = $page;
        return $this->view->url($params);
    }
}
  
Posteriormente lo uso en mis paginaciones:   
Código PHP:
Ver original<?php if ($this->pageCount): ?>
<div class="paginationControl">
<!-- Previous page link -->
<?php if (isset($this->previous)): ?>   <a href="<?php echo $this->urlParameters($this->previous); ?>">
    < Anterior
  </a> |
<?php else: ?>
  <span class="disabled">< Anterior</span> |
<?php endif; ?>
 
<!-- Numbered page links -->
<?php foreach ($this->pagesInRange as $page): ?>
  <?php if ($page != $this->current): ?>     <a href="<?php echo $this->urlParameters($page); ?>">
        <?php echo $page; ?>
    </a> |
  <?php else: ?>
    <?php echo $page; ?> |
  <?php endif; ?>
<?php endforeach; ?>
 
<!-- Next page link -->
  <a href="
<?php echo $this->urlParameters($this->next); ?>">
    Siguiente >
  </a>
<?php else: ?>
  <span class="disabled">Siguiente ></span>
<?php endif; ?>
</div>
<?php endif; ?>
  
Saludos.