In Outlook

  1. Click on File then Options.
  2. Select Search on the left then click Indexing Options.
  3. Click Advanced.
  4. Click the Rebuild button


That will take time - in some cases several hours if you have lots of email.