After having an issue where Registered Users were not receiving notifications, and extensive debugging, I wanted to share something that took me a long time to learn in case it helps anyone else:
Settings->Registered Users-> Compulsory Categories
While the checkboxes you check here will be checked by default, and unable to be unchecked, when users update their settings - this does NOT mean that all your registered users are actually subscribed to them. If you check a new category here, it will NOT subscribe Registered Users to them until that registered user goes to this screen and updates their settings.
I might suggest that this behavior is changed in the future. If I'm going to require them to subscribe to these categories, I might as well subscribe them to the category immediately!
Anyway, time to write a script to add a few hundred people to a few categories... :P