When an Internet search is activated Sherlock correctly sends an HTTP 1.1 style request to the proxy server. Unfortunately, the HTTP 1.1 "Host" header field is incorrectly filled in with the name of the proxy server instead of the hostname of the resource being requested. This can cause some newer HTTP 1.1 compliant proxy servers to drop the request and hence cause the search to fail.
Mac OS 8.5.1 resolves this issue. You can download the Mac OS 8.5.1 Update from Apple Software Updates sites.
Please see the following article for additional information:
Article 26165: "About Mac OS 8.5.1 Update"
This article can help you locate the software update mentioned here:
Article 14724: "Where To Find Apple Software Updates" - Lists online services for free Apple software updates.