вероятно, в этот момент вы уже нашли решение, но в поиске в Google я нашел эту тему, и решение состоит в том, чтобы не посылать ключ через URL, как вы делаете, вместо этого добавьте его в качестве параметра в запросе так:
string wsUrl = "http://dev.virtualearth.net/REST/v1/Locations/-30,-70/";
var request = new RestSharp.RestRequest(Method.GET);
request.AddParameter("includeEntityTypes", "AdminDivision1,CountryRegion");
request.AddParameter("key", myLey);
request.AddParameter("o", "xml");