We have found the issue. This case is simply never accounted for.
A solution is to call :notify_mailing_list_subscribers from the NotifyCategoryChange job. I have just verified that this is working.
Team, would you accept a PR for this or is this plugin territory?