There have been a few threads over the years about SM searches not working - I just added to the one noted below.  In short, I think a great solution would be to have the feature added to schedule automatic mailbox reindexing - either for a whole domain or for select mailboxes.  I think it would resolve a lot of frustration with using the UI for searches.  Thanks.

Here's the thread I'm referring to: