I'm reluctant to call this an answer, as it makes a number of assumptions that should probably be clarified with additional questions first, but here goes.
Assuming there's a piece of code somewhere responsible for adding something to the cache with the key "Animal_Vacinations", and that code knows what other cached items the "Animal_Vacinations" item is dependent on it, then that code should create each of the necessary cache key dependencies, including adding Null objects to the cache, if necessary, for any dependent items not already found there.
So, for instance, in the example you give, where there is already "Cat" in the cache prior to adding "Animal_Vacinations", then the logic responsible for adding "Animal_Vacinations" to the cache should check the cache for the existence of each dependent item, i.e., "Cat", "Dog", "Bird", "Jon Skeet"; when one isn't found, a placeholder object or boxed value (maybe an empty string) should be added to the cache for that key (in this case, for "Dog", "Bird", and "Jon Skeet"); once all of the dependent items exist in the cache, then create your cache dependencies and add "Animal_Vacinations" to the cache. (Alternatively, call Cache.Add with a placeholder object for each of the required dependent keys, without first checking if they exist with a Get, and use an exception handler to swallow the exception thrown if it already exists.)
Continuing your example, when subsequent to this activity a real something is added to the cache with the "Dog" key, using Insert instead of Add in order to account for the possibility that the key already exists (as it does in this example), then the replacement of the "Dog" cache item, which was simply a Null value, will trigger the invalidation of the "Animal_Vacinations" cache item per its cache dependency.