1. A system, comprising: a data store that stores a plurality of objects, wherein each of the plurality of objects comprises a user key and a version identifier, and wherein at least one of the plurality of objects further comprises object data; one or more processors; a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform: receiving a request to retrieve an object from the data store, wherein the request specifies a user key and targets a particular object version; and in response to receiving the request to retrieve the object: determining whether the particular object version is a delete marker object comprising the specified user key, wherein the presence of a delete marker object comprising the specified user key in the data store indicates a prior logical deletion of the specified user key from the data store; and in response to determining that the particular object version is a delete marker object comprising the specified user key: returning an error indication; and refraining from returning object data contained in the at least one of the plurality of objects stored in the data store that further comprises object data.