I also hate search. The other day someone gave me a tip though, which has helped quite a bit. The global search and the other search you get in your inbox suck so don't use them.

The actual search that works "okay" if when you right click on a folder and select 'Search Messages'. Sorry if you know this already, but I didn't know and it's so much better searching through this interface as opposed to the other two.