A method for recovering meta-data that has been subjected to corruption is disclosed for a cache memory. Each table entry in the cache memory has an in-cache indicator for indicating whether the data unit associated therewith is stored in a cache-slot in the cache memory. A first review is conducted of the table entries for identifying in-cache table entries (those that are associated with cache-slots in the cache memory), performing a correction attempt to ensure that the meta-data in an in-cache table entry are validated and corrected, if necessary, and ensuring that the in-cache indicator is set for an in-cache table entry. A second review is conducted of the table entries to ensure that the in-cache indicator is not set for any table entry that is not an in-cache table entry or for any in-cache table entry for which the correction attempt was unsuccessful.