> A non-existing resource doesn't mean it was deleted, but simply means it is not there - for whatever reason.

There you have ambiguity of using http codes for representing application logic. Using any other http code will have the exact same problem - you can easily encounter a situation when http-meaning is accidentally confused with your-definition, this was just one example. The solution is to not mix them at all.