Assuming it doesn't take too long to connect to the server and send an HTTP HEAD command, you could fake a GET request and see if it returns a 404 error:
<?PHP
$host = 'www.example.com';
$path = '/images/';
$img = 'myimage.jpg';
$fp = fsockopen($host, 80, $errno, $errstr, 30);
if (!$fp) {
echo "$errstr ($errno)<br />\n";
} else {
$out = "HEAD ".$path.$img." HTTP/1.1\r\n";
$out .= "Host: $host\r\n";
$out .= "Connection: Close\r\n\r\n";
fwrite($fp, $out);
$status = fgets($fp);
fclose($fp);
if(ereg('HTTP/1\.[01] 404', $status)) {
echo 'remote image does not exist.';
} else {
echo 'remote image exists.';
}
}
?>