I have using the Wordpress `paginate_links()` to build a paginator on a custom archive template for a custom post type. My site uses URL rewriting to build the pagination links:

    <?php echo paginate_links(array(
        'base' => get_pagenum_link(1) . '%_%',
        'current' => max(1, get_query_var('paged')),
        'format' => 'page/%#%',
        'total' => $wp_query->max_num_pages,
    )); ?>

This works fine until I try to add query string vars to build a custom search string when the paginator echoes:

    .../entries?post_type=entry&s=testpage/1
    .../entries?post_type=entry&s=testpage/2

Instead of:

    .../entries/page/1?post_type=entry&s=test
    .../entries/page/2?post_type=entry&s=test

and so on... How can I get the correctly formatted URLs?