I am having the same problem with 4.1.3 as well. When I use link:
www.domain.com/search.php?search=widget
and it brings back more than 1 page of results & I then use the same link again but change widget to another item that you know will bring back more than 1 page of results, it skips the first page of results on the second search.