Go to terminal
type
sudo mdutil -E /
this will reindex the Mac AND Outlook
I am not aware of anything that would make this not work.
Outlook mails are all stored in local files, just like Mail. The database contains the index of the mails etc, not the mails themselves.
If the above does not work, try rebuilding the Outlook Database. This is not as intrusive as it may sound.
Press down the Option key (between command and control) and while holding it click Outlook icon in the Dock. Click rebuild, the rest should be self-explanatory.
If this does not work, reply stating more install details. What Mac, what OS, what partitions etc.
Good luck!