is there a way I can create a rule which would target All users 'except' a certain set of tagged users?

@prabhat​ There are several ways to do that, depending on your workflow / the filter you want to use to differentiate between the users.

With most (maybe even all?) audience filters you have the option to choose "is not".

For example, if you want to send it to all users except for the ones you tagged "category X", you can filter the audience for:

Tag is not "category X"

That way the tagged users are excluded from the audience