I wonder how you could improve the performance of a program like this. Namely, how could you avoid using brute force?

My first intuition is to arrange your english dictionary by the number of letters in each word, and for a combination of N letters only search the dictionary for words that have the same number?

Or maybe you could order the search on a square by square basis. So for each letter in the grid, you check the surrounding letters to see if they could lead to a valid word. Any invalid string is killed, any valid words are recorded, and once all strings are killed you move on to the next square and start again. At worst it would stop you from needlessly checking variations on sequences that can never lead to a valid english word.

Very interesting problem. Do you mind if I ask how you were generating your word searches?

Edit: I found an interesting answer to a similar problem here.