I've jumped through a bunch of hoops trying to get Wordpress search to behave in a very specific way recently, in fact it annoyed me to the point that I wrote a small rant about it.
http://www.embracer.com/2010/priorit...ries-in-search
Search everything and search unleashed get my vote as well though, as far as the plugins go