What about using 403
for the first case (together with the explanation) and 404
for the second? Since the RFC 403 refers to 404 as an alternative response code they might be related...
403 Forbidden: The server understood the request, but is refusing to fulfill it.
Authorization will not help and the request SHOULD NOT be repeated. If the request method was not HEAD and the server wishes to make public why the request has not been fulfilled, it SHOULD describe the reason for the refusal in the entity. If the server does not wish to make this information available to the client, the status code 404 (Not Found) can be used instead.
403: You understand what the client wants but refuse to fulfill it. The client should not try again - it's forbidden until this resource is created - which you can explain as part of the answer.
404: You know that the client wants something you won't provide and can tell him in good faith, that this resource will never exists.
Update:
RFC 2119 explains how the "SHOULD NOT" has to be interpreted:
SHOULD NOT This phrase, or the phrase "NOT RECOMMENDED" mean that
there may exist valid reasons in particular circumstances when the
particular behavior is acceptable or even useful, but the full
implications should be understood and the case carefully weighed
before implementing any behavior described with this label.
I think for your use case this is true. The client request shouldn't be repeated *without solving the reason stated in the 403 answer: "accessing this resource is forbidden because no user named mario exists". But if the client is sure that the reason went away, he is free to try again. But this might be only my interpretation of the 403
"should not be repeated" statement.