So in essence, it sounds like the answer could depend on how the request is formed.
If the requested resource forms part of the URI as per a request to http://mywebsite/restapi/user/13
and user 13 does not exist, then a 404 is probably appropriate and intuitive because the URI is representative of a non-existent user/entity/document/etc. The same would hold for the more secure technique using a GUID http://mywebsite/api/user/3dd5b770-79ea-11e1-b0c4-0800200c9a66
and the api/restapi argument above.
However, if the requested resource ID was included in the request header [include your own example], or indeed, in the URI as a parameter, eg http://mywebsite/restapi/user/?UID=13
then the URI would still be correct (because the concept of a USER does exits at http://mywebsite/restapi/user/
); and therefore the response could reasonable be expected to be a 200 (with an appropriately verbose message) because the specific user known as 13 does not exist but the URI does. This way we are saying the URI is good, but the request for data has no content.
Personally a 200 still doesn't feel right (though I have previously argued it does). A 200 response code (without a verbose response) could cause an issue not to be investigated when an incorrect ID is sent for example.
A better approach would be to send a 204 - No Content
response. This is compliant with w3c's description *The server has fulfilled the request but does not need to return an entity-body, and might want to return updated metainformation.*1 The confusion, in my opinion is caused by the Wikipedia entry stating 204 No Content - The server successfully processed the request, but is not returning any content. Usually used as a response to a successful delete request. The last sentence is highly debateable. Consider the situation without that sentence and the solution is easy - just send a 204 if the entity does not exist. There is even an argument for returning a 204 instead of a 404, the request has been processed and no content has been returned! Please be aware though, 204's do not allow content in the response body
Sources
http://en.wikipedia.org/wiki/List_of_HTTP_status_codes 1. http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html