Very interesting. It makes sense that you could learn the model for something like classification which has a cut and dry answer. Just brute force queries at the API, log the results, and start working on your own model based on theirs.
To add insult to injury, you could outsource the training of your own model to the API too.
Alternatively, you could restrict your "stolen" model to a smaller domain and use fewer, more targeted examples for training. But at this point, you might as well start blending in predictions from other APIs, perhaps even training one off the errors of another. This is basically a technique that has been around for a long time, and in one incarnation is called "boosting" (see Adaboost).
With carefully selected queries based on an already trained model, I think you many not need so terribly many. But that's just an intuition.