To help narrow down the problem, you could print the value of HTTP_REFERER whenever the error occurs.

print "Content-type: text/html\n\nERROR - Invalid Referrer: ".($ENV{HTTP_REFERER} || '(null string)')."\n"

Note, however that you can't count on HTTP_REFERER having a value, in fact it's often not sent by the client and is probably the cause of your problem. You also cannot trust it, as it is easily spoofed, so that alone doesn't protect your script from being exploited by spammers.