ArcGIS Explorer 2500 uses the "geocode.arcgis.com" service.
This URL is the search for "redlands"
http://geocode.arcgis.com/arcgis/rest/services/World/GeocodeServer/findAddressCandidates?Address=red...
Does it return the JSON when you click the link?
[ATTACH=CONFIG]31741[/ATTACH]
Could there be something on your network that is blocking access to this service?
Mark