I'm really not sure why the REQUEST_URI seems to get reset - but I've heard of that before... I have used PHP scripts to handle error documents and with success. For example, go to http://www.hostfacts.com/foo.bar
and you'll see where it states "We could not find any file named /foo.bar". You could very easily mail this information out using:
"404 - $REQUEST_URI",
"404 Error - someone requested $REQUEST_URI and they came from $HTTP_REFERER"