The users/search endpoint does not return the most popular or followed users for a given query.
https://api.twitter.com/1.1/users/search.json?q=Bill%20Gates
Returns the same results that the actual Twitter search returns starting from after 2 or 3 results on the page.
I found this bug report that lists the exact symptoms that I am having. It says that this was closed about 3 weeks ago, but I do not see this being resolved.