Please note that I have not written very many validation formulas, but here is a suggestion that you may be able to apply to yours.
I needed to force users to enter an exact pattern for an alpha-numeric ticket number. On the Ticket ID# field's properties I set the default value to translate(Ticket ID#,"dax","DAX") - this made the text entered into the field all caps. Then I set a validation rule on the Ticket ID# field that checked the text entered into the field. The condition formula looks like this:
Ticket ID# does not match pattern custom pattern
The custom pattern is: [dD][aA][xX][0-9]{12}
Now users are forced to enter dax and 12 digits. If the pattern is not observed then the user gets the red box and an error message. (Note this does not validate against any other list. The text entered must follow the custom pattern.)
Perhaps you can rework the custom pattern to force the user to follow your acceptable pattern and then you won't have to check the data entered against the other list.