Instead of the Finder or the Dock, I use Spotlight heavily. I should probably move to Alfred, but I'm too cheap. I only notice it reindex after some upgrades and maybe once or twice a year otherwise.

I also use iOS search a lot and haven't run into the problems you describe. The iOS App Store? I'm on the same page as you. It's totally frustrating and doesn't work right.