The spec regarding this: "A successful response SHOULD be 200 (OK) if the response includes an entity describing the status, 202 (Accepted) if the action has not yet been enacted, or 204 (No Content) if the action has been enacted but the response does not include an entity."
204 is what I would return for most DELETEs because there is no status (entity) left after a normal delete.
As an API consumer, I would prefer a 404 not found - so that I may easily and accurately populate up the information that a resource I expected to be there, and to delete, wasn't there when I tried to delete it. Especially in complex applications where various clients may be running against the same data set across many distributed nodes, this can be demonstrative of many much harder-to-find problems when every action is "success."
I also would prefer 200 - with a description of the entity that was deleted, again, for verification and system maintenance needs.
Presumably, if you are logging status codes received by your client, you are also logging the requests that produce them; you should be able to determine if it is spuriously trying to delete the same resources from the request history. The only status code you need to make this determination is the 2xx received from the first successful request.
Consider that to catch two nodes deleting the same resource, you'd need to correlate the messages from all nodes. (Or, at least, know that there may be a problem with nodes trying to delete the same resource, and plan by recording every resource deleted in some other node.) Whereas, with a 404, you can determine that there is a problem in one message - and have the resource information to search through your history and find related events. Given that some of the systems I've worked in have had thousands of nodes - I'd rather not go through the log history from each node on every normal event to verify that it isn't actually abnormal. At a certain scale, relying on correlation and positive anomaly detection approaches such a level of difficulty as to be nearly impossible.
Generally, two nodes trying to delete the same resource isn't an anomaly. (The result of those attempts being something other than the resource being deleted exactly as if one attempt was made to deleted would be an anomaly, as it would the same node attmepting to delete the node more than once after having received confirmation that it had been deleted on an earlier effort.)
Because that is useful information. What benefit is there to hiding the information?
I think this is the crux of the debate is where do you draw the line?