Earlier quoted context omitted.
You might make this more obvious. Also, you might state how to distinguish between "sorry we need more time to look this up" and an actual 404 or error. HTTP code 202 Accepted seems appropriate for this ( http://en.wikipedia.org/wiki/List_of_HTTP_status_codes )
504 Gateway Timeout would be the obvious one, since if I'm reading this correctly it's essentially a timeout of zero; 5xx status codes are indicative of retriability later on. But I think that sort of performance would make the free tier essentially worthless. “All you have to do is hit our API endpoint, and BAM, you get results back.” Except you really don't. Analogy: a caching DNS resolver that returned an instant…
Thanks for taking the time to check us out!