The help and docs sites generated by softwares like HelpnDoc with tens of thousands of pages are also purely html with no database or dynamic elements at all. But their self-generated search on export works so great in the sidebar with their static site index for 1000s of pages. So if there is nice static-index generating search script, I think it can easily handle tens of thousands of posts.
When I was talking on WordPress plugins, I was talking of a specific plugin which I have used before, which has an option to actually build a static search text index file to cache and speed up the search with no load on the dynamic database whatsoever. And this worked fine with a blog with a 1000 posts too.