Solved! Go to Solution.
Keal,
There are older services around which may still work:
http://tasks.arcgisonline.com/ArcGIS/rest/services/Locators/TA_Address_NA_10/GeocodeServer
Regards
Anthony
P.s. You could always just download a shapefile of the cities and perform some sort of spatial join on your data:
http://www.baruch.cuny.edu/geoportal/data/esri/esri_usa.htm