Not to detract from Thunderbird's deserved attention, but I've been using Evolution for many years, and search is delightfully instantaneous.