Hear hear. If Airmail weren't so good in most other ways, the search would have caused be to abandon it long ago. As it is, I am searching constantly for a worthy replacement. For instance, Canary Mail has blazing fast search and looks good, but is missing a few features I rely on in Airmail. Fix the search, please, it's awful.
I'm a little reluctant to clean my cache, since I have a LOT of mail - but also, I'm thinking I need to start over to possibly clean some things out after years of use. I have LARGE files in Airmail - icons.db 4GB, bloopsearch2.db over 2 GB in one of my accounts, etc. If I clean the cache, will these files be recreated? Right now I have 22 GB total in the Airmail folder. I actually also have to use another program for searching, but so many things I like about Airmail keep me using it. Among all of the mail apps, I probably have half of my hard drive used up :-) - I guess I need to clear some things out!!! But I need a searchable client.