When you type a term into Mail's Search field, you can optionally select a person, subject, or other category from a pop-up menu to create a token that Mail uses to search one or more headers alone (such as To, From, and Subject). (If you don't explicitly select a header, or if you do but change the search token to say Entire Message, Mail searches message bodies as well as headers.) Surprisingly, Mail's system for indexing and searching headers is separate from its system for indexing and searching message contents, so searching for header text (say, messages from a certain co-worker) could fail even if the same message is matched during a search of its contents.

Mail uses a set of files collectively called the Envelope Index to index and search message headers. So, if you're unable to find messages when searching headers, there's a good chance the Envelope Index is having problems. The surest solution is to force Mail to rebuild the entire Envelope Index.

To do this, first quit Mail. Then, in the Finder, hold down Option and choose Go -> Library. Navigate to ~/Library/Mail/V2/MailData and drag the following files to the Trash: Envelope Index, Envelope Index-shm, and Envelope Index-wal. Open Mail again, and you'll see a message that Mail has to import your messages. Click Continue and let it do so; what it's really doing is rebuilding your Envelope Index. When this process finishes, try your search again.