If you can calculate the fitness at run time, then try all of the regex's and choose the match which matches using fewest wildcard matched characters. Are matches using a character set a lesser evil than those using .? Probably it's a function of the number of different characters that could have matched at each character location.

The fitness should also be modified by providing some weighting for alternate matches. Would you need to account for backtracking too?