Try Rebuild Outlook Index
i. Open Outlook 2016, Click the ‘File’ menu, select ‘Options’ and then choose ‘Search’ that is available on the left side of the window.
Or
Open ‘Control Panel’ on your Windows PC
ii. Click the ‘Indexing Options’ button and then ‘Advanced’
iii. In the ‘Advanced Options’ window, select ‘Index Settings’ tab and click the ‘Rebuild’ button
Note: A ‘Rebuild Index’ dialog box opens displaying the message that the ‘index might take a long time to complete.’
iv. Click OK to start rebuilding the index.
v. Restart Outlook to check ‘Search’ functionality, after the process to rebuild indexes completes