This looks promising. Runs MySQL Fulltext search, as well as integration with Google Custom Search Engine.
On the search results page you can refine your search by specifying whether to search posts, pages, and comments. You can also sort the results by relevance, date, or alphabet. The Advanced Search link leads to a form where you can specify author, categories, tags, and date range.
I haven't tested it yet though, so I can't officially vouche for it, but I'm really looking forward to playing with it. Built in WordPress search has sucked too hard for too long.