@Vero
I've gone through all the steps, and everything seems to be working now.
I suspect I haven't had Terminal in Full Disk Access before, not entirely sure though.
After the reindexing finished, and reloading alfred cache, I've managed to find every app I tried so far.
Thanks