Spotlight not finding some applications (ex. Spotify)

Hello,

I have this issue since a couple of months now, it is not consistent, sometimes the issue disappears then comes back again.

It is the following:

I open the Spotlight search via the keyboard shortcut (in my case Option+Command+Space) and type Spotify and the search doesn't list the Spotify app in the results. It does list websites, etc but not the application (please see attachment).

Yes, I do have the app checkbox selected in the Spotlight settings and it works for other apps (like Safari)

Any idea, what can it be?

Cheers

Janos