Hi,
Have you changed the search scope to All Mailboxes when searching in Online mode? Have you tried searching within OWA?
When Outlook is in Online Mode, the search feature passes the searching query to the Microsoft Exchange server, utilizing the Exchange search service. If the searching scope was selected correctly, this issue is more likely related to the Exchange search
service. I would suggest you Diagnose Exchange Search Issues as following links:
https://technet.microsoft.com/en-us/library/bb123701.aspx
http://blogs.technet.com/b/mspfe/archive/2012/04/27/how-to-troubleshoot-issues-with-exchange-2010-search.aspx
If above doesn't fix the issue, I'd recommend you post a new question in the Exchange forum to get further assistance:
https://social.technet.microsoft.com/Forums/office/en-US/home?category=exchangeserver
The reason why we recommend posting appropriately is you will get the most qualified pool of respondents, and other partners who read the forums regularly can either share their knowledge or learn from your interaction with us. Thank you
for your understanding.
Steve Fan
Forum Support