Ok. I've been looking into this searching thing for days now. I'm up to my neck in character sorting, fulltext indexing, trie's, and more. Here's what I found.
If you're using mysql, its pretty easy to have a pretty powerful and quick engine by using mysql's ability to generate indexes on text, such as the comment, the title, etc. However, if you're using an even newer version of mysql (of the 4.x alpha variety) you will have access to a complete set of boolean operators for searching. Even better.
That's with mysql. If your copy of MT uses DB_File instead, I'm still looking into it. DB_File doesn't store robust record sets, it only stores key/value associations, from what I've read.
Oh well. I might never end up doing anything with any of this, but its interesting to research at least.
Required reading: Advanced mysql Searching.