- First thing to do would be to Rebuild your Outlook Indexes
- Control Panel – Indexing Options – Microsoft Office Outlook – Advanced – Rebuild
- Change the Default PST file from your Outlook Profile to Mailbox
- Open Outlook
- As the Index Rebuilds; please try to do a search from your Mailbox Contacts; it should work perfectly.
- Once the Index is completely rebuilt; you can revert back the default data file to your local PST