Hey there, Follow these steps:
Select Troubleshoot search and indexing.
Select your problem from the list and click Next.
Choose Try troubleshooting with administrator permissions
If the troubleshooter can fix the search issues, then try to perform a search with Cortana
I don't think this applies to W10 Mobile, does it?
March 2019 update seems to have fixed this issue (at least for me).