1.

Start WIndows go to Controlpanel/ Programs and Features

Go to " Windows Features activate and deactivate"
2.

Switch OFF "Windows Search"

Windows will start a reconfiguration and ask for a restart, do so 
You now removed this feature from WIndows and with it all faulty settings that cause the problem
3.

After the Restart open Outlook

Office will start a reconfiguration, that`s good it now removes the Windows Searchoption from Office, and with it all your problems 
You will note that you still bew able to search but your options are very limited. 
You can not search for Emails with attachments. I tryed to life with this limited Search. Its not worth it!
4.

Enter something into the Outlook searchbox

Outlook will complain the the Searchfunktion is not working. That is correct cause we just deleted it.
5.

Close Outlook restart WIndows

If you make changes in the Windows Features an additional Restart is an healthy thing.
6.

After the restart go to Controlpanel/ Programs and Features

Go to " Windows Features activate and deactivate"
7.

Switch ON "Windows Search"

Windows will start a reconfiguration and ask for a restart, do so. 
Now Windows will reinstall the Searchfunktion brandnew and clean.
8.

After restart go to Controlpanel/ Indexing Service

Click on "Change" and "Rebuild the Index" 
Make sure that Outlook with the correct User Account is in the list on the left Side 
Now that you have a brandnew Search Funktion installed you have to rebuild the Index
9.

Open Outlook

While the Index rebuilds Open Outlook and enter something into the Searchbox and Outlook will tell you that the search results are incomplete 
Have patience
10.

To check the progress

In the Ribbon Menu "Searchtools" you find a dropdown button "Searchtools" there you find the option "Indexing Status"

There, Outlook will tell you how many Items still need to be Indexed, this number should go done while you rebuild the Index.

If you enter something in the Outlook Searchbox you can watch more and more results appear