paginate_links() don’t properly work in search.php?

I’m fairly certain this is answered elsewhere, but I’ll add it here again.

I believe your issue lies here:

'current' => max( 1, get_query_var('paged') ),

Try this instead:

global $wp_query;
$wp_query->query_vars['paged'] > 1 ? $current = $wp_query->query_vars['paged'] : $current = 1;

…then:

'current' => $current;

Your 'base' may also be an issue. Instead of this:

$big = 999999999;
//...
'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) )

I use this:

'base' => @add_query_arg('paged','%#%')

Edit

In case it’s helpful, here’s my entire paginate_links() wrapper function:

/**
 * Paginate Archive Index Page Links
 */
function oenology_get_paginate_archive_page_links( $type="plain", $endsize = 1, $midsize = 1 ) {
    global $wp_query, $wp_rewrite;  
    $current = get_query_var( 'paged' ) > 1 ? get_query_var('paged') : 1;

    // Sanitize input argument values
    if ( ! in_array( $type, array( 'plain', 'list', 'array' ) ) ) $type="plain";
    $endsize = absint( $endsize );
    $midsize = absint( $midsize );

    // Setup argument array for paginate_links()
    $pagination = array(
        'base'      => @add_query_arg( 'paged', '%#%' ),
        'format'    => '',
        'total'     => $wp_query->max_num_pages,
        'current'   => $current,
        'show_all'  => false,
        'end_size'  => $endsize,
        'mid_size'  => $midsize,
        'type'      => $type,
        'prev_text' => '<<',
        'next_text' => '>>'
    );

    if ( $wp_rewrite->using_permalinks() )
        $pagination['base'] = user_trailingslashit( trailingslashit( remove_query_arg( 's', get_pagenum_link( 1 ) ) ).'page/%#%/', 'paged' );

    if ( ! empty( $wp_query->query_vars['s'] ) )
        $pagination['add_args'] = array( 's' => get_query_var( 's' ) );

    return paginate_links( $pagination );
}