The mini I-CSCF in the stateful_proxy module uses 404 Not Found, with the rationale that this should be the same as if the LIR/UAR look-up didn't find a suitable S-CSCF at all.

I just checked TS 24.229 - it addresses the case where the HSS returns a negative response, but doesn't say what to do if the response is bad (for the negative response case, it says the I-CSCF should use 480 Temporarily Unavailable for REGISTERs and 404 Not Found for other requests).  I would suggest we follow the negative response status codes.