Energy storage is unique in that it can provide multiple services. This feature raises cost-recovery issues for storage, due to the combination of competitive markets and ratebased cost recovery used in many power systems today. This hybrid regulatory paradigm relies on classifying assets as providing competitively prices or unpriced services and handling cost recovery based on that classification. Some recent regulatory precedents suggest that storage developers must choose between classifying their assets as providing competitively priced or unpriced services. In the former case, storage costs must be recovered through the market. If an asset is classified as providing only unpriced services, costs can be recovered through the ratebase. This regulatory design can hamper cost recovery for storage and may lead to inefficient storage investment and use. We propose an alternate solution whereby storage-capacity rights are auctioned to third parties that use their rights for priced or unpriced services. Storage-capacity rights disentangle storage cost recovery from the regulatory treatment of its end use. We formulate the storage-capacity auction model and demonstrate how to efficiently price storage-capacity rights. We show that the revenues earned by the storage owner through the auction equals the imputed marginal value of storage capacity, as revealed by the market bids.