To fix this issue, you will have to reset the search index to force the Exchange Search service to index all items in the Mailbox Database including items that were moved to the database from Exchange 2003.

To reset the search index, open up the Exchange Management Shell navigate to:
%PROGRAMFILES%\Microsoft\Exchange Server\V14\Scripts

then run the following command:
.\ResetSearchIndex.ps1 -force -all

You should see output that resembles the following:

WARNING: Waiting for service ‘Microsoft Exchange Search Indexer (MSExchangeSearch)’ to finish stopping…
MSExchangeSearch service stopped
Deleting catalog for Mailbox Database
removing: D:\Exchange Server\Maillbox\catalogdata-your catalog ID

MSExchangeSearch service Started

To verify that the rebuilding of the index has completed do the following:

You will receive MSExchange Search Indexer Event ID 109 when the full crawl begins.
You will receive MSExchange Search Indexer Event ID 110 when the full crawl ends.

You should now be able to search for pre-transition items using Exchange search.