A new Geoprocessing tool, that can geocode addresses in a FeatureClass/Table using the Bing Maps Geocoding would be beneficial. Now the users need to utilize the Bing REST API via Python and implement the response processing.
It's inputs can be similar as for the Geocode Addresses Tool. The Bing key could be one extra parameter. (Note that the ArcGIS Server users have already the Bing key).
