I'm curious about how many users are on your organization's Slack. I consider it one of my go-to sources for my org that has had between 250-300 people for the past 3 years. I can see it being suboptimal for a bigger company, though.
I'm in an organization with many thousands of people and find search to work very well.
Does the pricing plan influence the amount of resources your organization can use? e.g. slow search on the free plan, but much better on Enterprise Grid.