Lucene performs extremeley well, given the correct configuration. We run a few lucene indexes, the largest of which contains well over 3 million records, and our site averages close to 2MM daily pageviews.
Our average query response time (95th percentile) is ~80ms, and we serve thousands of requests per day using a RAM-based servlet configuration in Caucho Resin.
The search algorithm is a standard TFIDF algorithm (with some additional gravy), which can be easily extended or replaced given that the source code is well designed. I would highly recommend this package, having used it over the past 3 years in a variety of applications.