Outlook 2013 search broken after upgrade from 2010


Outlook version
Outlook 2013 32 bit
Email Account
Exchange Server
We recently upgraded our Citrix servers from Outlook 2010 to Outlook 2013. We are using Outlook with an Office 365 E3 plan using redirected .ost files and Cached Exchange Mode.. Previously, the search functionality in Outlook 2010 seemed to work fine. Once we upgraded to Outlook 2013 the search results are empty. I do notice that the Search Tools > Indexing Options area does not show the Outlook profile like it does on a computer with Outlook installed locally. Microsoft support confirmed that the search functionality will not work with redirected .ost files and they say that the search mechanism from 2010 to 20103 has not changed. I find this hard to believe as it worked prior to the upgrade. Just wondering if anyone else out there is using a similar setup and having better luck with the search inside of Outlook? Thank you. Paul Abke