Previous guidance I've seen suggests that:
* "Create me this resource, and tell me where you put it" is implemented with POST.
* "Create me this resource right here" is implemented as PUT.
According to the HTTP 1.1 RFC:
"The fundamental difference between the POST and PUT requests is reflected in the different meaning of the Request-URI. The URI in a POST request identifies the resource that will handle the enclosed entity. That resource might be a data-accepting process, a gateway to some other protocol, or a separate entity that accepts annotations. In contrast, the URI in a PUT request identifies the entity enclosed with the request -- the user agent knows what URI is intended and the server MUST NOT attempt to apply the request to some other resource."
Creating when you know the key is, in my mind, creating where you know the URI. So I'd implement it as PUT. After all, PUT typically means "cause a future GET to this URI to return this value, without concern to previous server state." That without concern part means that it should handle both creation and update.
Given that, then you don't need to solve your problem. It's all previously-solved cases. A create-PUT is just a PUT with an ETag of "is currently missing" and succeeds iff that resource is in that state.
Of course, this works if you are making a REST API, but will confuse people who are using a more constrained meaning of the verbs (such as ATOM's mapping to CRUD).
Arlo