Some additional information:
I made a change in a template in hewiki, that should have removed some 400+ pages from some maintenance category.

The category page count started dropping slowly, and got "stuck" on the way down for periods of tens of minutes.
the job queue length (action=query&meta=siteinfo&siprop=statistics) hovered around 600-700 for most of the time, and went down to ~60 after completion (this is

during the time it was stuck, i opened several pages that appeared in the category. none of those pages showed the category. purging the page did not remove it from the category, but null edit did.

similar change to remove 12 more pages did not complete after 20 minutes or more, getting stuck on 7 pages (none of which had the category), while job queue seems "stuck" around 700-800.
once the category emptied, job queue dropped to ~60 (this was done in an off-time for hewiki - around midnight ust,)

this experiment is very easy to perform, even on a live wiki - as long as hidden category is used, there should be no effect on readers.

REPLICATION

1. choose a live wiki, containing at least one template with moderately wide transclusion (several thousands)
2. create a hidden category
3. choose a template which is transcluded in ~2000 pages on some wikipedia. select a template which is not transcluded as a parameter of another template, but rather directly on the page
4. count the number of pages transcluding the tempalte (e.g., using hastemplate: search)
5. add the hidden category to the template.
6. measure how long does it take to the category to get populated in full
7. remove the category from the template
8. measure how long does it take for the category to empty

HTH

peace.

Tentatively adding "Discovery" here but I might be wrong...

If I'm understanding correctly here, this primarily concerns categories. Categories are not something that currently Discovery handles, and this doesn't actually appear to be search related, so I'm removing the Discovery tag. :-)

This is a long-standing problem. See T69419 and this discussion from 2014.

Here's another example: I created "Category:Pages using invalid self-closed HTML tags" on 14 July 2016 on en.WP after a change to MW started adding a hidden category to articles with a specific kind of HTML error. As of today, 28 Sep 2016, there are pages on en.WP such as "Portal:East Frisia/Region" that have the error in their code and will properly appear in the category after a null edit, but that have not yet shown up in the category on their own.

That means that fundamentally, categories are not being applied to articles in a timely fashion until those articles are edited. By any measure, taking more than two months to properly apply maintenance categories to pages is a bug that needs to be fixed.

Is there some way that we can force all pages to be null-edited (or the equivalent) with a reasonable frequency? It is not happening right now.

[edited to add:] I have been informed that changes to MediaWiki code that result in maintenance categories and changes to templates/modules that result in category changes are processed differently. This may be two different feature requests.

@tstarling, @ssastry, and I discussed this a few days ago in #mediawiki-parsoid. Tim proposed modifying the refreshLinks.php script to support queuing jobs to update pages based on when they had last been parsed (using page_links_touched). After an initial run, we should set this up as a cron job.

In T132467#2674866, @Jonesey95 wrote:

[edited to add:] I have been informed that changes to MediaWiki code that result in maintenance categories and changes to templates/modules that result in category changes are processed differently. This may be two different feature requests.

Now that I've fully re-read your comment, it's different than what this task is about. I've forked it to T157670: Periodically run refreshLinks.php on production sites..

In T132467#3004685, @Legoktm wrote:

@tstarling, @ssastry, and I discussed this a few days ago in #mediawiki-parsoid. Tim proposed modifying the refreshLinks.php script to support queuing jobs to update pages based on when they had last been parsed (using page_links_touched). After an initial run, we should set this up as a cron job.

not familiar with the fine technical details, but there is something worth noting:
in my experience (i think it's mentioned above), action=purge does _not_ fix the situation for a specific article - only a null-edit does.
so if "someone" creates such a cron job, please make sure this "update pages" the job executes is equivalent to null-edit rather than "purge" (in my naive thinking, there should be no difference between purge and null-edit, but it is very apparent such difference exists.
i will not be shocked if it turns out this difference is the root cause of the issue, and maybe fixing "purge" to do exactly what null edit does is the _real_ fix here.

peace.

This is still a problem. See https://en.wikipedia.org/wiki/Template_talk:Infobox_settlement#Category:Wikipedia_page_with_obscure_country_or_subdivision_and_this_template for a recent discussion where only about half of the articles had been updated after a month.

We're at least five years into this problem, with no fix (or workaround, like manually queuing unrefreshed articles, as discussed in T157670). It would be great to have a backstop for this problem so that no page could go X days without a refresh, for some reasonable value of X.