When I search for e-mail, not all of the messages matching my search show up in the results.
When Windows Mail downloads a message, it immediately adds the e-mail addresses and message title to the search index. However, the body of the message is indexed along with all of your other Windows files, and may not be added to the index immediately. Wait a few minutes and try your search again.
Also, Windows Mail only searches the currently selected folder for messages. For example, if you select the Sent Items folder, messages in the Inbox, Outbox, and other folders will not be included in the search results.
Note: This information provided by Microsoft.