I'm confused; your thread title references security yet your only question seems to be about efficiency. The two topics are rather orthogonal, so I'll just go with the actual question...
For one, note that the 'Referer' header is completely optional and can even be intentionally disabled by user preference or simply stripped/filtered by intermediate gateways/proxies.
Instead, I would use $_SERVER['REDIRECT_URL'], something that should be set assuming your webserver is Apache and you've used the 'ErrorDocument' directive to handle 404 errors.
EDIT: Woops, missed the point that you're trying to get the page before the error. In that case, ignore the last bit about $_SERVER['REDIRECT_URL'] and simply know that you may get e-mails with no values for the referring URL.