[eluser]louis w[/eluser]
The project that I am speaking of is a cms. So whenever you save a page or a page which is linked to another page in the admin then I clear all respective cache records.
Additionally, for something like a user-gen site, whenever a user updates his/her profile you clear their profile's cache record (and maybe the directory too).
Whenever a request is made to an item if a cache record doesn't exist, the system creates one for subsequent requests.