I am running ArcGIS 10.3.1 on two different computers. I have a server set up with data on it, including a few address locators. On my machine, I can connect to the folder on the server and add any of the address locators and use them without issue. On the other computer, going through the same workflow, I get an error message that says "Address locator is damaged." This happens with Esri's Street_Addresses_US locator as well as a couple of different local address locators, created by different entities.
The only difference in these two machines is that mine is on a different image that the other. I am an administrator on my machine and it is set up without any restrictions. The other is set up as a public access machine with restricted rights by our IT department. That is the only difference between the two computers, which leads me to wonder if there is something there that might be interfering with loading the address locators?
Everything I've found online has to deal with using address locators set up in different versions of ArcGIS, but I've got the same version on both computers, and it works fine on one, but not the other.
I am experiencing the exact same problem you describe. I do not have any custom locators setup. The only locators that appear are the MGRS and World one from Esri.
I wonder if your firewalls are not allowing traffic through.
I can access everything else on the server just fine, even through ArcMap. I'm not aware of anything special in a locator file that would cause errors where other files wouldn't.
I tracked down my issue. I just spend thirty minutes on the phone with my IT department. Some how our web filter lost my login information so by default it was blocking stuff that I previously had access to because I was not a named user anymore. By chance are you running a Barracuda Web Filter? We installed new firmware on ours last week and it seems like since then it's been blocking stuff like crazy. IT logged me out of the web filter and I restarted my computer and once I logged back in and accepted the web filter agreement everything works.
I just had the IT department log on with their administrator access and they still got the same error. So that leads me to believe that it's not a firewall deal.