PHP get's its $_SERVER from the server. Unless its set up to NOT send the referrer, than apache will provide the HTTP_REFERER to PHP.
Since it works intermittently, I wouldn't be surprised if its simply that 50 - 60% of browsers are not providing their referrer to you. There's nothing to be worried about though; the referrer carries 0 value to it. The most useful purpose of it overall is to help support a session verification method.
BTW, if you are getting links from a particular location, that would indicate you can control the links or get in contact with someone that can. Add a querystring to it to determine where the linkback comes from.
header('HTTP/1.1 420 Enhance Your Calm');