I've been thinking about this problem, since it's going to get even worse with the new preprocessor. Currently, links in unfollowed branches aren't registered, but templates *are* registered in both branches. So if you have:
{{#ifexist: test | {{a}} | {{b}} }}
Initially [[test]] doesn't exist so {{a}} is displayed. Then [[test]] is created and the HTML cache for the page is invalidated via pagelinks. But the links tables are not updated, so although the page now contains the contents of {{b}}, it doesn't have a template link to it. So when [[Template:B]] is subsequently changed, the cache is not invalidated.
The solution is to add yet another tracking table.
Ah, I see the problem now. Is a whole new table really required? Can't #ifexist just be made to update the links table?