Its a blessing that the project keeps going strongly.
Often, though I know exactly the info required to find a message, Thunderbird comes up with no results. I've found that "repairing" the containing mailbox renders the message findable.
Not sure when things got this bad, but I can well recall in the past Thunderbird's search being fast, thorough, and reliable.
Quick search is where it's at. Keeps the view sane and you select which fields to search (subject, recipients, body), the downside is that you have to know which folder to look in, which can also be an upside to narrow it down (I know that's also possible in the search UI but this is easier)