You would need to stop the service first (it creates a lock on the locator), rebuild the locator, then restart the service. I would imagine that you can create a batch script for this and schedule it as a Windows event to happen every night at a specific time.
I am asking how you published the data. This means, did you publish it by referencing the locator (creating a data store that pointed to the locator on disk) or by copying the locator to the server (no data store)? If you published it by referencing it, then my suggestion would work. If you published it by copying the locator to the server, then you will need to re-create the service by referencing the locator instead of copying it.
Another question. Where is your locator stored? I see you mention SDE is where your address points are located but where do you store the locator?
The Address Locator was created and is stored on our server, in a folder where all of the MXD's reside that are used to publish the map services which are consumed by our viewers. The Address Locator was then published as a geocoding service to the same location on our server that we publish our map services too. I am enclosing a screen shot of the Address Locator properties.
If you try to publish the locator one more time with a different service name, can you tell me if it prompts you with a dialog entitled "Copying Data to Server", with the following text "Datasets that will be copied to the server:", and the name and path of the locator that you will be copying?
This is what I am trying to figure out. If the above happens, you don't have your data folder registered with Server so your data will be copied to a known ArcGIS Server folder for use instead. If you want to learn how to register your data with Server, read the following help topic:
I maintain a point feature class in a SDE database (sql server back end) but I replicate them to a file geodatabase. My locators point to that replica data and the locators are published. All my data maintenance is performed via SDE. After I sync my changes from parent to child (SDE->FileGDB) I stop and restart the published service. The locators themselves are stored in their own directory, not an object of the fgdb. With the published service stopped, I rebuild the locator and then start the service back up. Works like a charm.
It never hurts to dump the REST cache as well (http://servername/Arcgis/rest/admin ). Stopping and starting the service should invalidate the cache anyways, but we've had to manually clear the cache at times in order to see updates.