The fastmail web client is actually decent as such things go, and its search works ok. When I have trouble with Thunderbird search I sometimes log into Fastmail and use their web client.