I've found that REFERER is one of the least dependable of the CGI variables. It seems almost anything can block the information - security settings on browsers, security settings on firewalls, browsers using different interpritations of the HTTP spec (some only report referer on POST and not the more common GET).
Also, a side note, I hate the REFERER is misspelled.