REST API v3 Request /user/search doesn't work for 10% of companies


We’re facing the problem with getting users into plugin. About 10% of the companies get us nothing for the request.

We use REST API v3 Request

I know there is a method /rest/api/3/users/search

But according to the doc an application is not allowed to use this method.

Question: why it can happen? How can we solve this problem?
If there is magic under the hood, then how can we use this method /rest/api/3/users/search to get data into plugin?