Could I make a recommendation (feel free to ignore it).

There is a way to delete your search dB (its an sqlite file in your profile (but google first for instructions), and leave it rebuild (depending in your mailbox size it can take a day or two).

I had to do it once when I moved a bunch of folders.

The search should be instant.

It does take a few secs to start but a while back I created a new profile and imported my old rules etc and it's much quicker to start now.