HTTP_REFERER is simply an HTTP header the browser sends, clients like wGet can send any HTTP headers they want, PHP's fsockopen() will allow you to do the same.
Some older browsers / browsers which don't behave simply neglect to send HTTP_REFERER headers.
If a person doesn't come from a page, ie they just type your domain name in or use a bookmark, HTTP_REFERER most likely won't be sent.