Here's another one for the "I should have done this a long time ago" list. I had been experiencing some problems with mt-search.cgi on this installation; it was using up too much memory on the server (this is also why I switched to using Tagwire for showing my tags).
Now I'm using the PHP-based Fast Search and it works great. It took me a little while to figure it out but once I got it down, setting it up for each of my blogs was a snap. You can test it out using the search form in the sidebar of the blog.
The one oddity I found, which may be due to something weird on my end, is that it didn't like the "fastsearch" filename for the search template and the Dynamic Pages Error Template would claim "Page not found". This caused me a lot of confusion. However, I found that it worked fine if I used a different output filename for the template. The rest was easy from there.
This is a great plugin and I especially recommend it to anyone who finds that mt-search.cgi is slow or is using up too many server resources.