Just came to report that this is the case with enwiki too - may be separate, but could be related; haven't opened a separate ticket, but if I should I can.. Also, using Quarry, I found that, after 159.50 seconds and without the 5000 page limit, there are 44229 categories that are empty and not marked with expectunusedcategory, while, after filtering out those in the category "Wikipedia_soft_redirected_categories", the total number was significantly lower, at 1034 pages, and only took 8.18 seconds. Would it be possible to allow on-wiki configuration of what is excluded?
On Commons, I went through Special:UnusedCategories and touched all pages several times (as this method affected only the 5000 pages that were listed, so after each run more and more redirect categories came up), and I believe the list is (mostly) correct for now.
When editing templates it is necessary that the job queue is refresh all pages to store the new page property in the database, because the special page needs it in the database.
It is possible to do it with a null edit if needed.