Hi Carl Sack
One of the times I saw this issue (World Geocoding Service not appearing in Locate pane), we determined it was because the user had their organization URL set up as the active portal (e.g. "https://ess.maps.arcgis.com"). Once we switched this to the general ArcGIS Online portal ("https://www.arcgis.com"), it was resolved. You might want to give that a shot.
In regards to the Rematch Addresses issue, this one has me stumped. What version of the software are you on? Might be good to upgrade to 2.3 if you haven't already. Also, are you using a custom locator or the World Geocoding Service here? Can you reproduce the issue if you geocode the same table again with the same locator? What about with different locators or different input tables?
I'd recommend you reach out to Esri Support if you're still having trouble with this, and we'd be happy to help you get back up and running!
-Eric