Don't know what happened with iOS 16, but Spotlight has been painfully slow. Results used to be nearly instant, now it can take 6+ seconds to show an app I searched for
I installed a few apps since upgrading to iOS 16 when it came out, and those apps never show up in Spotlight. I've updated with patches, restarted the phone, deleted and re-installed since then; still broken. The main one is Slack but I've seen it with others, too.