Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances
Here's the first approach that occurs to me.  Build a complete graph on 11,000 vertices, and label all edges with the great-circle distance.  Apply some travelling salesman algorithm to choose the best route you can find.  Then, for every edge on that route, query the map service for the road distance and replace the label on that edge with the road distance.  Then, apply the travelling salesman algorithm again on the modified graph.  Repeat this basic process until it converges.

I think the great-circle distance should be a lower-bound on the road distance, so I suspect this should be correct (in the sense that it doesn't miss out on a better solution).

One possible complication is that this might cause triangle-inequality violations, so if you are relying upon a heuristic that assumes the triangle inequality, this approach might screw things up.  I don't know; you could try it out and see.

If you wanted to reduce the number of queries for the road distance even further, here's one more idea you could try.  I suspect that the smaller the great-circle distance, the closer it is to the road distance; or, in other words, I suspect the gap between the distances might be largest for points that are far away.  That's something you'd need to validate yourself.  If it is correct, then a variant of the algorithm I suggested above is: only query the map service to obtain the road distance for edges where the great-circle distance is above some threshold.  (You could even gradually reduce this threshold in each iteration of the above algorithm.)