Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently efficient.
If we are talking about words of a sufficiently small length, then you can just precompute the answer in advance. I.e. word cut will be in an answer for masks ___, c__, _u_, cu_, etc. For words of length at most 5, it'll result in $\le 2^5 \cdot10^5$ memory, which is of order of few MBs.
If the length is big, then you can split the mask into two parts. For each part, we find all the answers, and then intersect them. For example, we treat mask a_b_c_d_e_ as an intersection of a_b_c|_____ and _____|_d_e_. For both submasks, we find the set of words containing this submask, and then intersect them. If the final answer is small, then, hopefully, the result for at least one of these submasks will be small. You can also try to select the positions to include into each submask randomly.
For even bigger lengths, you can split the mask into more than $2$ parts. However, you can probably use that there are not many very large words and simply enumerate them all.