What about this:
We render page, mark places with broken links by: "\0article name\0html for broken link\0" and put that into cache, plus we put 0 in some_links_fixed field. We also update some broken_links table.
Script then gets page from cache: if (some_links_fixed == 1) { get list of all broken links (trivial) check which got fixed fix link html code for them update cache (no full rendering, only replace links that got fixed) set some_links_fixed to 0 } else { convert all \0x\0y\0 to y (trivial) }
Then if some article is created, all pages which link to it get some_links_fixed set to 1. If some article is deleted, all pages which link to it get cache invalidated (much rarer event).
Now Main Page, and all pages with no broken links, get rendered only once !
Well, we could also postpone rendering of variables by some similar trick.
It would be better if it was inside some transaction, as there is small race condition associated with some_links_fixed.