Photos app in iOS 18.5 apparently not indexing photos, so very limited search results - how to fix?

I'm not sure what you've tried. Have you done a forced re-start?

Force restart iPhone - Apple Support

This is different from a simple Power Off. I had to continue holding the button down past the "slide to power off" message, and then I released the button only after  the Apple Logo appeared indicating a re-start. 

Since scanning uses the battery, and since lots of people are very anxious about battery drain, the iPhone will avoid scanning when not plugged in. And since scanning uses processing power, and people hate slow downs, the iPhone will avoid scanning while you use it. And since scanning requires bandwidth, the iPhone will avoid scanning when the internet connection is weak.

So, if you want faster scanning, then find good wifi, plug the phone in, and leave it alone. All this applies to a lesser extent for the Mac.

In Settings>Apps>Photos, be sure to turn on Enhanced Visual Search,

and turn on Settings>Search>Show related content.

And wait-- it can take a long time (a week, or more, probably) to scan through all your pictures…