Searching only works for exact match names

Some time ago, I had to process (unzip/delete) millions of files. This would be slow with the Search Indexer running, so I kind of stopped the service and disabled the settings allowing it to run.
I re-enabled everything, but now searching:
- only works if I type the full name of something in the Start bar - eg typing Whats won't find WhatsApp
- only looks in the current level directory

Any idea what I should check? thanks.

I wish mine works like yours. It gives me so many options....

Use * and ? character.
For example, to search for WhatsApp you can type *whats*.* for any file that has whats or Whats???.*

Thanks! this only works for the start menu, though.

Folder searching doesn't work