Unfortunately, after most iOS updates or after restoring a phone from a backup, Spotlight seems to stop finding apps until I open the app I'm looking for, for the first time.
This is a reproducible problem that I've noticed for at least a year. Here's what it looks like along with my workaround.
1. Confirm that the Applications option is checked and it's at the top of your Spotlight search setting.
2. Search for the app that Spotlight can't find. In my case, I was looking for my little-used eBay app. Sure enough, it didn't show up in Spotlight.
3. Search for the app in the Apple App Store. The App Store knows if you've already installed an app so that you don't need to redownload it. If an app is already installed on your iPhone, the GET or $x.xx button will say OPEN. Tap the OPEN button and the App Store, which is hundreds or thousands of miles away, will find and open the app that Spotlight, running on your own phone, couldn't find.
4. Once I've opened the app and then closed it, it magically appears in future searches. As a matter of fact, once I've gone through this exercise it seems that Spotlight is now primed to find other apps too.
Postscript: I've also seen a similar issue when searching for people or text in the iPhone's Messages app, but I haven't found a work around for that, yet.