Eureka! I've got it!!
Give each page a "links complete" bit.
The first time the page is loaded, we check all the links, then set the
bit ON.
After that, any page change (creation, deletion, etc.) WHICH AFFECTS
THIS PAGE would then turn the bit OFF.
For example, a page with 20 links. Half of them are to existing (blue)
articles. Half are to missing (red) articles. We load the page, figure
out the colors, cache the page, and set the bit ON.
Next time, someone loads the page, we chech the bit. If it's still on,
we serve the cached copy. (Cold cash! Cash and carry! We get a
substantial discount!!!)
But --
If anyone creates a new page, we take some extra time to trace all the
"pages that link here" and turn off each affected page's "links
complete" bit. (We do not have to re-render the page, though. That can
wait.)
Likewise, if anyone deletes a page.
(patting self on back)
Uncle Ed Poor
Resident genius, tame creationist, and brainwashed cult member ^_^