This post is one of the ways to resolve Windows 10 start button search not working.
After I fixed it then it works again like below.
I am using solution 9 below but before that I do a complete Disk Cleanup using File Explorer.
Then I issue this command.
DISM /Online /Cleanup-Image /RestoreHealth
Somehow it has nothing to do with Cortana for my case.
Nothing works for me in this long blog.