I observed this behavior on my site but I actually managed to reproduce this on phpbb.com:

Go to http://www.phpbb.com/community/search.php and look for "modder convertor" selecting the option "Search for any terms". There are 7226 matches, but if we click on page 2 on the results page we'll receive an error "No suitable matches were found."

The search "modder convertor" selecting the option "Search for all terms" returns only 1 result, so there's no page 2. I guess this is the reason for the error. I think this is because the "terms" parameter is lost when going from the first page to the second and this option default is "all" instead of "any".

PS: I've searched the bug reports and found nothing related to this. I apologize if this is repeated elsewhere.