This is definitely a tricky problem to solve! Generally, with APIs that have limits and limited ability to search, users have to employ a solution like this:
That way, they can kind of have the best of both worlds.
Otherwise, have you looked into the Query JSON with SQL query type? I kind of explain it in this answer here, but let me know if you have any questions at all!
http://community.retool.com/t/search-textinput-from-api-get-response/17580