I agree, the search is quite bad.

The UI is bad and the results seem to be poor. I don't necessarily have the issue that emails are not in the results, but more that results are too numerous and the only way I can narrow down results is putting more constrains in the UI. What often happens for me is that I search using a several terms or some specific phrases and the search returns tons of results (does it just do an OR between words in the search) and I then end up clicking (why can't the time constraint be a slider?!) through different months (based on what I recall about the timeframe of the email) until I find the email.

When I was using notmuch I recall results being much better.

Another annoyance is that Thunderbird only seems to search locally, i.e. if I don't have some folders downloaded it will not do a server search as well as a local search (maybe there's a setting for it?)