Hi,
This all could be solved very easily.
Since you want to match only at least one of the selected categories, and nothing else, you might not need the exclusions at all, there is a different option. So, to solve this:
1. On the Frontend Search settings -> Advanced panel, change the Category/Taxonomy terms logic to “At least one selected terms should match”: http://i.imgur.com/nPlpTT0.png
2. (optional) You can unset the exclusions now (Advanced Options -> Exclude results), as it’s not neccessary with this logic: http://i.imgur.com/ErUsERO.png
This should result in the exact same behaviour as you described.