For existing apps:
I had this happen too with 2 zone lookups. Nothing had changed with the apps or services, they just stopped working. My fix, for EXISTING apps, was to open the app config search tab, add the whole Esri World Locator (we were using a geocoder view that we created to limit the extent), and re-publish the app. I was even then able to go back in and REMOVE the entire Esri world locator, keeping the limited geocoding view still there, and re-publish again, and now they work.
Keep in mind we had the ArcGIS World locator registered as part of our Org the entire time. this seemed to be more app specific.