Does looking at the response headers or content of the 404s show anything of interest? If you have control of the webserver, on a 404, verify that the request looks correct, too.