After 2 days trying to solve it, I did it.
What helped me was:
1. Disable and re-enable the search feature using CMD:
dism /Online /Disable-Feature /FeatureName:"SearchEngine-Client-Package" (after you disable it you need to restart windows).
dism /Online /Enable-Feature /FeatureName:"SearchEngine-Client-Package"
2. Reinstall Cortana Search App from Powershell
a. Press WIN+X keys together to launch WIN+X menu and then click on Command Prompt (Admin) option. It'll open Command Prompt as Administrator.
b. Now type Powershell in Command Prompt window and press Enter. Wait for a few moments and Powershell session will be initiated in Command Prompt window.
c. Now type following command and press Enter:
Get-AppxPackage -Name Microsoft.Windows.Cortana | foreach {Add-AppxPackage -register "$($_.InstallLocation)\appxmanifest.xml" -DisableDevelopmentMode}
3. Now open configuration > Cortana and select permissions from the left list. Now activate Cortana and what it can do. After doing this, my search worked again.
I hope it helps you guys! :)