You should have the online locators listed under the available locators, not sure why they're not there. Can you go to your Catalog window > GIS Server > Add ArcGIS Server. Choose the Use GIS Services option and then for the Server URL on the next page, enter:http://tasks.arcgisonline.com/arcgis/servicesThis offers a location where you can use the online locators. Try to add them to the list of available ones through ArcMap, or just access the locator within the tool by navigating to that new GIS Server connection.