A data storage system, employing cache and base storage, assigns an “anywhere” token to each data object received for storage, whether the object is stored in cache or base storage. The anywhere token contains the latest metadata for the data object and includes at least a version code. If a data object is stored in base storage, the data object is assigned a “base” token with the same value as its anywhere token. These “cacading” tokens are available for use in tracking functions such as cache grooming, de-staging data to base storage, and processing cache miss events. All tokens are stored in a token database. For each data object, the token database lists its anywhere token and base token. If the storage system experiences a cache failure, normal storage operations are halted until the cache is repaired. Then, the controller implements a replacement token database. Namely, the controller accesses base storage to retrieve tokens of all data objects lost from cache. Using these base tokens, the controller populates a replacement token database, inserting the retrieved base tokens as both base and anywhere token for each data object lost from cache. Then, the replacement token database is used to the exclusion of the previous token database. With this procedure, the newly created token database accurately represents the contents of tape and cache. This avoids any danger of unknowingly recalling down-level data objects from tape, where their current counterpart data objects were stored on cache but lost in the cache failure.