Coincident with ArcGIS 10.1 SP1, the on-line geocoding locators visible to ArcGIS for Desktop were replaced by the new World geocoding service. This service provides street-level geocoding for many more countries than the previous services and will continue to expand in coverage and take advantage of continuous updates, like ArcGIS in general.
Using your organizational credentials, you can add the GIS Service from http://geocode.arcgis.com/arcgis/services and perform batch geocoding. Interactive address finding and address inspection against this service is available from the geocoding toolbar in ArcMap and does not require authentication.
Batch geocoding using the World service requires an ArcGIS Online subscription and will consume credits. Please see a description of the service here:
The old locators used prior to SP1 are currently still accessible at the following URL, but will go offline at some point in 2013: http://tasks.arcgisonline.com/arcgis/services
Why has Esri made this change? We have built the World service in partnership with data partners; you will appreciate it takes considerable resource to capture and maintain the world’s address information and build it into reliable high quality web services. Batch geocoding consumes millions of transactions daily here at Esri; while we cannot absorb the rapidly growing cost of global demand for this we will continue to support free map navigation and address inspection using the World service.
Esri also ships free geocoding locators for the US in the Data & Maps media that ships with ArcGIS, and of course we also supply locator definition files for the US, so you are able to make locators using your own data sources.