Let me try to draw the picture for you.
To get notified you start by the service which has to be checked and change the state, this has to be the same in your case.
Next step is the notification object which is defined with a state and type when a notification should be send and a user (group) it should be send to. So here you could differentiate by creating to different notification objects for User_A and User_B which differ by the state attribute.
Last step for the notification would be the user object which also has state and type to decide which notification he wants. So you can also differentiate at this level between User_A and User_B.
So what would I do? It depends why the users want different notification setups and on the scope. If User_A always wants all and User_B always only want critical, then I would do it on the user level, if it is for a very specific service I what do it by creating different notification objects.
And one last thing: I really hate if people only want critical notifications, because critical means something is broken so people are only reacting, warning means something is going to break and people can react proactively before something has an impact to a service.