Mark,
I think the issue is that it is backwards from what you were saying. The pipeline is searching if the Employee ID in this other table does NOT equal (or contain, I tried that as well) the Employee ID from the Multi-Select Field that could potentially have multiple Employee IDs selected.
My other thought with this if the pipeline itself cannot do this is some formula that would parse out the responses of the multi-select field into individual separate text fields, and then I can have the pipeline ensure each of those is not contained in the search. Is that somehow possible?