You would first need to create a connection to ArcGIS Online through "GIS Servers"/"Add ArcGIS Server" in Catalog (URL = "http://tasks.arcgisonline.com/arcgis/services"). Once you have established this connection, you will be able to add the locator to the model.
Brad
What version of ArcGIS does it work on and which one does it not work on?
Brad