How to enable Views caching for all pages instead of only the first page?
While I haven't used a search view, I ran into a similar problem with pagers. Views caching has two parts out of the box, query and render. The render cache was interfering with the pager. I think setting the Views caching to Search Specific is setting both query and render in one swoop. 

I would try changing it to Time Based and caching the query, but not the render. Varnish will then be able to correctly cache the various pages of the view.