When you search your inbox by copying a word from a message subject and searching for it by subject … but get nothing back, that’s a good indication that the content index database has gone corrupt. With Exchange 2013, you can manually reinitialize that database as follows:

Stop-Service MSExchangeFastSearch
Stop-Service HostControllerService

rename “C:\program files\microsoft\Exchange Server\V15\Mailbox\Mailbox Database 1440585757\1CDB1E55-A129-46BC-84EF-2DDAE27B808C12.1.Single” “c:\program files\microsoft\Exchange Server\V15\Mailbox\Mailbox Database 1440585757\1CDB1E55-A129-46BC-84EF-2DDAE27B808C12.1.Single.bad”

Start-Service MSExchangeFastSearch
Start-Service HostControllerService

# Wait a bit for the content indexing process to start
Get-MailboxDatabaseCopyStatus | FL Name,*Index*

ContentIndexState of “Crawling” means it’s still working on it. Healthy means it’s done.