If reference data is stored in a feature dataset and the Create Address Locator tool is run from ArcCatalog, either from the ArcToolbox window, the Search window, or by right-clicking on the geodatabase and selecting New > Address Locator, the default Output Address Locator location is in the feature dataset, which is not supported. This does not occur in ArcMap from the Catalog window, ArcToolbox window, or the Search window.