I would definitely be interested in knowing why it is hard. And yes, I was thinking about lookup: for example from (1) a dictionary, (2) a set of proper names and (3) a set of previous crossword answers. While nothing is perfect, but this (from an armchair) seems like it should work pretty well. And I am not proposing it as the main part of the algorithm, just a check on non-words.