OK, try the following:
OMG - I just realized that Restrictions has a specific option for Podcasts, and seeing as how you can't see the app or download it, I'm thinking that may be the issue. Go to Settings>General>Restrictions, and see if you have Restrictions turned on. If you do, then make sure that the Podcasts option is turned on to "Allow" it. All of your "symptoms" point to that being the issue đ
If that is not it, then you can try the following:
1. Completely close out the App Store (and the iTunes app, if it is open) - double click the Home button and then swipe up on the App Store (and iTunes if it is there) app to close it.
2. Sign out of the iTunes & App Store by going to Settings>iTunes & App Store, click on your Apple ID, then click on Sign Out. Sign back in again and see if you can find the Podcasts app.
3. If that doesn't work, sign out again, then reset your device: Hold down the Home and Power buttons (or the Volume Down and Power buttons for an iPhone 7) at the same time, and continue to hold them down until the Apple appears (up to 30 seconds). Once the Lock screen displays, try the search again.
4. If that doesn't work, try resetting your Home Screen Layout: Settings>General>Reset>Reset Home Screen Layout. This will return the layout of your Home screen to the original layout, so you may have to rearrange things later, but it also might reveal the Podcast app.
5. Finally, if none of the above work, then make sure you have a current backup of your device in iCloud, iTunes, or both, then go to Settings>General>Reset, and Erase All Content & Settings. Set up the phone as a new device (not from the backup), and try the search to see if you can find it. If you can, then you can Erase again, and then set it up from your backup, and then do the search again to see if it will show up. If it does, you are all set. If it doesn't, then that would point to some kind of corruption of the information on your device, and you would have to Erase and set up as new again, then manually set it up from scratch. This scenario is highly unlikely, since we are talking about seeing an App. But it is the last "test" in the string.
Best of luck,
GB