¿paginate_links() no funciona correctamente en search.php?

Estoy usando esto en mi plantilla search.php...

<div class="pagination">
    <?php echo get_pagination_links(); ?>
</div>

Y esta es la función...

function get_pagination_links() {
    global $wp_query;
    $big = 999999999;

    return paginate_links( array(
        'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
        'format' => '?paged=%#%',
        'current' => max( 1, get_query_var('paged') ),
        'total' => $wp_query->max_num_pages,
        'prev_next'    => false
    ) );
}

-

La salida funciona: Si busco "test" y hay más de 10 resultados, la paginación muestra 1 2 donde 2 es un enlace. Al hacer clic en la página 2, la barra de direcciones se actualiza correctamente a mysite.com/search/test/page/2 pero la página resultante sigue siendo la número 1.

Siguen apareciendo los mismos resultados que en la página número 1 y los enlaces de paginación siguen siendo los mismos - 2 sigue siendo el enlace y 1 es la página actual.

¿Alguna idea de por qué podría suceder esto?

Actualización

Aquí es donde se llama la función personalizada en la plantilla:

<?php
/**
 * La plantilla para mostrar páginas de Resultados de Búsqueda
 */

get_header(); ?>

<?php if ( have_posts() ) : ?>
    <hgroup class="section-heading wrapper">
        <h1>Resultados</h1>
    </hgroup>

    <section id="results">
        <?php while ( have_posts() ) : the_post(); ?>
            <ul class="event-items">
                <?php get_template_part( 'inc/search', 'result' ); ?>
            </ul>
        <?php endwhile; ?>
    </section>

    <div class="pagination tiny wrapper">
        <?php echo get_pagination_links(); ?>
    </div>

    <?php else : ?>
        <div class="wrapper">
            <h2>No se encontró nada</h2>
        </div>
<?php endif; ?>

<?php get_footer(); ?>

Edición

Usando el código recomendado de la respuesta de abajo:

/**
 * Enlaces de paginación para búsqueda y archivos
 */

function get_pagination_links() {
    global $wp_query;
    $wp_query->query_vars['paged'] > 1 ? $current = $wp_query->query_vars['paged'] : $current = 1;
    $big = 999999999;

    return paginate_links( array(
        'base' => @add_query_arg('paged','%#%'),
        'format' => '?paged=%#%',
        'current' => $current,
        'total' => $wp_query->max_num_pages,
        'prev_next'    => false
    ) );
}

La paginación funciona ahora, sin embargo, los "permalinks" no son exactamente como quiero que sean. Uso custom_pagination_base() para tener esta estructura de permalinks:

• mypage.com/search/term/seite/2 (donde "seite" es la palabra alemana para "página").

¿Es posible mantener los permalinks funcionando así? La paginación funciona con tu código, solo que los permalinks se ven así:

• mypage.com/search/term?paged=2