Slack's advertisement for unlimited users was based on their product's design. Their hard limit is perfectly reasonable because the interface wasn't really designed to handle 10k users in the first place.
To complain about this is like buying a sailboat and complaining when you sail it into a hurricane.
Marketing materials are designed to show the intended audience how they may use something. Slack was created for use by teams, teams that know each other and that need to collaborate. Within that context, a limit of 10000 users is pretty reasonable because it IS 'unlimited' for their target audience who will never need 10000 accounts.
Again, the sailboat analogy. I was sold on my sailboat being 'seaworthy'. Does that mean it can literally handle anything the sea throws at it? No. It's a label used to show the target audience how they may use it. If I choose to sail into conditions it wasn't designed to handle, it isn't the builder's fault, it's mine.
With a 10,000 search limit, I don't see why Slack needs to limit users. Without search, it's mush less useful and borderline unusable with over a thousand users or so.