Disable SSL. - or -
Create direct connection to GIS Server by accessing the service from: https://geocode.arcgis.com/arcgis/services.
In Catalog make the connection, enter credentials, and add the 'World' locator to arcmap to geocode successfully even with SSL enabled. (This is for 10.x versions before 10.4).