Validation on a combination of fields

Our application will have multiple add forms where the user will need to enter/select at least two pieces of data before the form will allow the record to be added. These two entries must form a unique combination before they are valid.

What is the best approach to show a user that a combination is valid? I've used an error provider on the first field in the past that shows up once both pieces of data have been entered.

I've thought about using a status area at the bottom of the form to notify the user that the combination of data is not valid.

This is a simplified version of one of these forms. A name can only exist in one department. I'm struggling with how to display that either one of these items might be wrong. The user may need to change the name or select a different department. I have no way of knowing which piece is actually wrong.