Hi I had this problem too, and none of the rebuilding, etc., worked. Here is what I did.
I went to my Library by holding down the option key while clicking on File > Go (to reveal the invisible library). Then I went to Preferences and found com.apple.finder.plist BUT I ALSO found an additional file named something like com.apple.finder.plist.XXXXXX (with random capital letters where the Xs are).
That seemed fishy to me, so I compressed both plists into an "archive" (just in case I was wrong) and deleted the uncompressed versions.
Then I restarted my computer so it could make a new .plist to replace the one(s) I trashed. Out of curiosity, I also went back into the Library to see if I had TWO new .plist files and of course there was only one—as I suspected should be the case. How did the other one get in there? Hack? Virus? Glitch? I don't know. Anyway, I trashed the archive to get rid of it and my mail search function is running normally now.
Hope this helps!