I have noticed that when I specify a search query with posts_per_page equal to X, when the setting for "blog pages show at most" is Y, if X is less than Y, WordPress will show some 404s.
Here is an example to make it clearer:
Let's say under my admin settings, I set "Blog pages show at most" to 12. In search.php, I put:
<?php $posts=query_posts($query_string . '&posts_per_page=7'); ?>
Let's say a user searches for a term with 26 posts as a result. If I had not put my custom posts_per_page in search.php, the result would show in 3 pages:
first page: results 1 - 12
second page: results 13 - 24
third page: results 25 - 26
But since I specified posts_per_page as 7, it should show 4 pages of results:
first page: results 1 - 7
second page: results 8 - 14
third page: results 15 - 21
fourth page: 22 - 26
The first three pages load fine, but then when I click "next page" for the fourth page, WordPress still thinks that there are only three pages to show, so it will give a 404 on the last page.
This can be easily fixed by making sure that the value for posts_per_page is greater than or equal to the number for "blog pages show at most". But I think it should work in both cases. :)