I recommend you download and use a local locator from the ESRI Data and Maps DVD. You can get this at your customer care portal (customers.esri.com) under Software Downloads. There are some limitations with the free ArcGIS Online locators for batch geocoding. They are really meant more for geolocating with the geocoding toolbar or the Find tool, and not for batch geocoding jobs. Depending on the load the servers are getting, it could fail out for batch geocoding jobs, as they weren't really designed for this purpose. I recommend you either create your own Address Locator or download the Data and Maps DVD, which has several locators based of street map data. This will be a more reliable workflow for large jobs, such as what you describe.