Might be worth checking the handlers you have configured n web.config against other versions you know work. Could be the order is wrong and/or there is some other handler interfering with the execute request that's been generated as a result of the 404.

David

This is what I use in web.config

<httpErrors errorMode="Custom" existingResponse="Replace">
  <remove statusCode="500" subStatusCode="-1" />
  <error statusCode="500" path="/500.html" responseMode="ExecuteURL" />
  <remove statusCode="404" subStatusCode="-1" />
  <error statusCode="404" path="/404" responseMode="ExecuteURL" />
  ...
</httpErrors>

The only difference is the statusCode removals but this makes no difference to my issue. And David, there's very little modification of the core handlers, apart from a media handler for gated resources but I wouldn't think that would make a difference 

I would personally make the web.config as default as possible then add each customised element in one by one until you find the problem. My spider senses are tingling about the "media handler for gated resources" - perhaps it treats the ExecuteURL requests from IIS weirdly? Also does the request ever get to your 404 controller or does it hand before executing it? Does it happen on "/i-dont-exist/" and "i-dont-exist.jpg" and "i-dont-exist.aspx" requests too?

You know the solution better than I do so its something to debug through the logs or NewRelic I think :)!