remove_query_arg() on rewrite rule

I’m attempting to add a Back to Search Results link which in essence will simply link back to the starting search page – for example /?s=test. I’ve taken a look at the global query vars and do see there is a paged query argument available — which does do the job when the permalink structure is set to the default – for example /?s=test&paged=2 run through remove_query_arg(array('paged')) corectly becomes /?s=test. But, when you visit a second page of search results and you use anything but the default permalink structure – it is not removing page/2 which is what the default pagination structure outputs.

I believe I could just use $_GET['s'] and append that onto the site URL.. but I figured I’d ask here to see if there is a better way to do this. Thanks!