Tried Evolution, but it felt like such a step backwards in terms of features
that I sucked it up and lived w/o search working. Was about a year ago when I
last tried, and Evolution was horrible comparatively. KMail might have had
broken search, but Evolution was missing a whole pile of simple/common
features I used day-to-day. After a week, a went back to KMail and sucked it
up.