I have 5 accounts set up in Mail app. Everything has always worked well except for the $%&@! search function. It's the stupidest implementation I have ever seen. I have double-checked that messages are saved for offline viewing and made sure Spotlight is indexing etc. As a separate function the Finder search pretty well but even that is weird sometimes. Lately it's telling me nothing is there when stuff clearly is. Mail search is completely useless though. It seems to only search the from data even though I have clearly selected all.