I was thinking about these issues, too. And my conclusion was that if we indeed run into this problem, then qLabel was much more successful than I expected :) -- which would be awesome!
My understanding is that it will take quite some uptake to make a serious dent on the server requirements of Wikidata or Freebase (not sure about any23). Also, this uptake will be gradual and growing slowly, so we should have the time to react to that.
You already sketch out a few possible solutions. They sound reasonable.
What I am much more worried about is that we -- if my understanding is current and correct -- do not even count accesses to the Wikidata web API, in particular not which modules are called. So, in short, we actually have no grasp at all as to whether this API is called, how much it is called, usage patterns, etc. This makes it very hard to talk about it and to consider any solutions.
So, whereas I fully understand your concerns and I appreciate the suggested solutions, I think our first task in this direction is to actually start gathering more data, and set up counts and metrics for the API. Anything else would be just guesswork.
(In case we already gather these metrics, I would be very interested in seeing them!)
Hope that makes sense,
Denny