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.