It's not bad - their time range narrowing graph thingy is really good, and I can normally find what I need. My main complaint is that my outlook calendars don't show up, so I can't search them for events.
My biggest complaint is that there is a hardcoded result limit. And it searches for that whole limit, then renders the result. So if you have a lot of messages you can't use the date range thing to refine the results. And if you want one of the recent ones you still need to wait for the UI to lock up and return all of the results.
I'd say that's an exaggeration but it's not great. It would really help if you could default search queries to the 'show results as a list' and quickfilter view, but for some reason that's not an option.
Sadly, I have the same experience. It's one of the minus points of using Thunderbird, alongside the lack of the feature for shipping my configurations (e.g. filters) across machines.