Depends on too many factors for even a ballpark. Take Google's Machine Vision API for instance. The limiting factor here is that the larger your model (and deep networks are very large models in terms of free parameters), the more training data you need to make a good approximation. To come close to "stealing" their entire trained model, my guess is that your API use would probably multiply Google's annual revenue by a small positive integer.

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).

You don't need to steal the whole model. You can train a model yourself, and just "steal" those "bits" of a model that you can't reach with your own training data.

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.