Mail.app search useless?

I'm running Mail.app in 10.8.2 and I can't get search to do anything. I'd type something into the upper right search box and get no results. I've tried choosing different folders in the top horizontal bar that appears ('All', 'Inbox' etc) to no avail.

Mail.app is configured to work with IMAP accounts. The best I could coerce results is if I sometimes search for an email address but it would not be a complete list.

All the IMAP folders have been downloaded locally. I can browse folders and instantly look at emails from years ago.