I had this problem some time ago. And like you, I hated the idea of using the clunky standard two-columns interface for inclusion and exclusion. So I decided to make something like this instead.

Basically I let the user add groups, and then create the exclusions within each group. I also used an Autocomplete control that helped the user find the correct name of the groups.
My users in my test seemed to understand what was going on, but if you want to be certain, I would recommend you to test it on your users. This interaction model assumes that you will need to include something before you can exclude it. I do not know if that may be an issue in your particular problem.