Here's my setup:
ErrorDocument 404 /404.php
Now if I trigger a 404, say by going to http://localhost/this_file_doesnt_exist.php?foo=bar then I have these variables available in the $_SERVER superglobal:
[REDIRECT_ERROR_NOTES] => File does not exist: c:/program files/apache group/apache/htdocs/this_file_doesnt_exist.php
[REDIRECT_QUERY_STRING] => foo=bar
[REDIRECT_REQUEST_METHOD] => GET
[REDIRECT_STATUS] => 404
[REDIRECT_URL] => /this_file_doesnt_exist.php
[REQUEST_URI] => /this_file_doesnt_exist.php?foo=bar
Now, you may not have all of these (or any) if you're not running PHP as an ISAPI module with Apache.
At any rate, you should always have the REQUEST_URI index, as bpat pointed out, so try that if all else fails.