Permalink settings and search result pagination – problem?

I am using permalinks set to “post name” (example: xxx.com/the-post-name/)

The theme I am using generates search results in pages, using following code:

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

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

However, while the first page of returned results is fine, the subsequent pages do not work and just bump me back to the home page.

The URL produced is xxx.com/page/2/?s=searchterm

This doesn’t seem right and in any case, doesn’t work.

Is there something wrong in this code, or is there something wrong with the way my permalinks are set up?