The use of search extensions such as Lucene (http://www.mediawiki.org/wiki/Extension:Lucene-search) will help overcome the setbacks of MediaWiki's search facility.
Personally I haven't tested any of those extensions. Running a relatively small corporate wiki hasn't given need for advanced search requirements - at least not yet!
One thing I would like to share though is how to tag your pages with keywords you don't necessarily want to show as content on the pages.
Lets say you want a page called 'Test', which contains steps to install a printer, to show up each time a user searches for words like HP, Xerox or Lexmark. You don't want these words to appear on the page itself coz you've got nothing to say about them. I simply use the basic HTML comment tag!
Yeps, as any MediaWiki user will know, there is a list of permitted HTML tags which can be integrated in the Wiki Markup code.