Oliver,
The behavior you are encountering may be related to the bug described here, NIM091041: "Rebuilding or creating an address locator fails for specific enterprise geodatabases."
http://support.esri.com/en/bugs/nimbus/role/beta10_1/TklNMDkxMDQx , which was fixed at version 10.3.1.
The issue is that the string that is being passed for the index name of the command 'TableCreateLongIndex' doesn't have an index name, so it defaults to the fully qualified object name. If the 16th character happens to end with a period, the index fails to create. If the joined database and owner name of the locator table is truncated to 16 characters that result with a period or any special character at the end then the locator fails to build and the _LOX table is left within the SDE database. For example, the fully qualified name of the locator index table is "CONCORD.SDE.Streets_CreateAddressLocator1_lox", but when the index name is truncated to the 16th character the result is "CONCORD.SDE.Stre", which does not end in a period or special character. The locator is created in this case. However, when the fully qualified name of the locator index table is "CONCORD.SDEUSER.Streets_CreateAddressLocator1_lox", the truncated index name is "CONCORD.SDEUSER." , which ends in a period and the locator fails to create and you are left with the _LOX table.
In addition to Joe's response about not storing address locators within an SDE, it is not recommended that address locators be stored in any format geodatabase for performance reasons and if it is to be shared, it should be published to ArcGIS Server and shared as a geocode service. ArcGIS Pro does not support address locators stored in geodatabases and version 10.4+ will not either.
-Shana