Methods and apparatus for efficient recovery of cached volumes at storage gateways are disclosed. To recover, after an unplanned shutdown, a storage gateway appliance configured to cache chunks of a storage object, chunk metadata corresponding to a particular chunk is read into an in-memory metadata region from a first metadata location. Based on analysis of the chunk metadata, a validation requirement indication for the particular chunk is stored, and the chunk is designated as being accessible for client I/O requests. In response to receiving a subsequent I/O request targeted to the particular chunk, the chunk metadata is validated using a different metadata location prior to performing the requested I/O operation.