WP pagenavi给出了找不到的页面

I have a page which is displaying search result for my site. The query for the search results is like this:

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;

//Final post array with filters
$args = array(
   'post_type' => 'stores',
   'posts_per_page' => 24,
   'post__in'      => $store_ids,
   'suppress_filters' => true,
   'post_status' => 'publish',
   'paged' => $paged
);

I added WP pagenavi in the template to paginate the query like this:

wp_pagenavi( array( 'query' => $the_query ) );

This shows a nice pagination with the right amount of pages when I initially come on the search results page. But when I click to the next page I get a page not found page which off course shouldn't be happening.

The initial url of the results page:

http://www.website.com/?cat=44&s=1011AB&range=3

The url when I navigate to another page and which doesn't work:

http://www.website.com/page/2/?cat=44&s=1011AB&range=3

Does anyone have an idea how to get this to work?