Short answer is that 404
is the correct way to go.
Long answer is that the HTTP status codes relate to state transfer between the client and the server, and are NOT designed to indicate any issue with the server's database data model. The server is for the most part a black box to the client when it comes to the HTTP layer.
To clarify my answer I'm going to expand a bit as to the purpose of the HTTP.
HTTP is a REST protocol (if you use it correctly). And REST is representational state transfer. You transfer the current state of a resource (through a representation) between client and server without concerning yourself with what the resource might actually be
Why doesn't HTTP (or any REST protocol) want to know what the resources themselves are? Because that ties the protocol to the specific domain that these resources represent. A resource might be a customer of a bank. Inside the bank there will be a whole load of business logic as to what a customer can and cannot do, how a customer should be represented, how a customer should be validated etc etc.
If you were building a non-RESTful system that talks between client and server you would probably build into your client server communication protocol a lot of that business logic. You are building a one of system that is specific to your organisation, why wouldn't you. You might have an end point on the server called "validate_user" that you call with RPC, and part of your communication protocol might be "transfer user data" or something like that. You would build a protocol that is very domain specific.
Now there is nothing terrible with that, but it means that protocol is not very generic, and it also means that any time you change your business logic you also have to change your communication protocol.
That problem is what REST architecture is trying to avoid. It decouples the communication protocol from the business logic.
What REST architecture says is lets build a protocol that is only concerned with the transfer of a piece of data's current state between a client and a server, and not concerned what that data actually is or how it will be used. We will leave that up to the client and server to figure out.
The advantage of this is immediate, you can use that protocol anywhere you want to transfer data. This formed the basis of the web because the HTTP can transfer a piece of data like a HTML page, or a PNG image, or a mpeg video or a xls spreadsheet without ever having to know what it is, or why you want it.
The domain specific information lives at the client server level not the communication protocol level. Where is this domain specific information? It is in the Content Type, which the client and server can understand if necessary. The HTTP knows nothing about the content type other than the name (HTML5, PNG, MyBankUserCustomFormat etc)
My web browser understands HTML 5, but the HTTP 1.1 protocol doesn't. My Photoshop app understands what a PNG image is, but the HTTP 1.1 protocol doesn't. My bank client might understand what a BankUser is, but the HTTP 1.1 protocol doesn't.
I might point Photoshop at a remote image I want to edit. I request it using HTTP GET request and I get a copy of it, HTTP doesn't care what it is. My Photoshop app does, it cares that it is PNG imagine and understands what that means. I edit it, save it and PUT it back on the server. The server may or may not care what it is (say this is a custom server that validates changes to the image to see if they are too dark, or some other business rule). Again HTTP doesn't care.
So how does this relate to HTTP Status Codes. Well just like all of HTTP the status codes relate only to the transfer of the resources between client and server, not the resources themselves or why you are using them.
If I request an image from www.nytimes.com and they don't let me have it because a judge has ruled that the New York times is violating US copyright law by giving out imagines over the web and the New York Times have spent a few million implementing a new custom web server that is fully aware of all the copy right logic the HTTP status codes don't change. There is no HTTP status code for that on purpose.
And you shouldn't try and figure out what one best fits to some how communicate this new copyright law business logic to the client via the HTTP protocol. HTTP Status Codes relate to the business domain agnostic problem of transferring a resource from the client to the server and when that doesn't work they tell you why only in the context of that process, not any wider business logic reasons.
Building a system where 404 doesn't just mean resource not found but now means something specific to your domain (say you decide it means that a database lookup failed and the client is supposed to stick an A in front of the user id and try again) just gets you back to the problem REST was trying to avoid, you have tied your communication protocol to your domain logic. If you change this in the future (actually lets not make it stick an A in front, lets make it a T) you have to change the HTTP layer of all your clients and worse the client has to know if it is talking to a server that interprets 404 the new way or the old way. Clients have to know not just the content type the server is giving them but also what specific server it is talking to and the specific way it is interpreting 404 responses.
So where do you stick this logic. You stick it in the Content Type. HTML 5 is quite different to HTML 4, and modern browsers understand both. Old browsers don't understand HTML 5, but they still understand HTTP because that hasn't changed in over a decade. So it is easy for your server to decide that if it is talking to an old client just give it a representation of the resource it does understand. If the server only understands new versions it can say I can't give you any version you will understand, stop asking. All this can take place without the HTTP changing. HTTP can last for ever without having to be changed or re-interpreted.
You should be coming up with custom content types that both the client and server understand, versioning them so that changes don't break old clients, and leaving the HTTP to the sole business of state transfer.
That is the RESTful way.