I think you're correct, actually. If you want to create a new object, it should be a POST. In a well designed RESTful service, a PUT on an object that doesn't exist should fail, and both of the PUT/DELETE orderings above should result in the same state of the world: the object does not exist.
I thought so too, but when I looked at the spec [1], it agreed with the others:
>>The PUT method requests that the enclosed entity be stored under the supplied Request-URI. If the Request-URI refers to an already existing resource, the enclosed entity SHOULD be considered as a modified version of the one residing on the origin server. If the Request-URI does not point to an existing resource, and that URI is capable of being defined as a new resource by the requesting user agent, the origin server can create the resource with that URI
