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, wherein at least two of the plurality of objects further comprise object data, and wherein at least two versions of at least two of the plurality of objects correspond to respective access control lists; 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, from a requester, to retrieve a particular access control list corresponding to a particular object version of a particular object from the data store, wherein the request specifies a user key; and in response to receiving the request to retrieve the particular access control list: 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 particular object from the data store; determining whether the requester has permission to retrieve the particular access control list; in response to determining that the particular object version is a delete marker object comprising the specified user key, returning an error indication; in response to determining that the requester does not have permission to retrieve the particular access control list, returning an error indication; and in response to determining that the particular object version is not a delete marker object and that the requester has permission to retrieve the particular access control list, returning the particular access control list.