I'm using an IIS server, therefore pretty permalinks still has /index.php/ placed in the url.
When using pagebar on search result pages Index.php is put into the url, so a page not found comes up when clicked on.
e.g. http://www.mydomain.com/index.php/Index.php/page/2/?s=searchterm
it works fine on every other page.