Идем в Файл -> Параметры -> Поиск. Выбираем кнопку "Параметры индексирования". Затем выбираем Outlook и жмем "Изменить".
Здесь надо открыть вложенные элементы у Outlook и проверить что стоят галочки на всех присоединенных к Outlook pst файлах. Снимаем эти галочки и закрываем Outlook. Через пару минут включаем Outlook, заходим в окно, где снимали галочки и ставим их заново. Жмем ОК и через пару минут все заработало.