Larger databases (10000 records and more) may require a better database environment. On shared hosts, you might experience issues with such number of posts (regardless of the search plugin). In this case you might want to consider switching to a basic VPS. It provides much better performance, yet it's still cheap.