Yes. As I indicated in my original post, known vocabulary is one of the factors that can be used for a configurable difficulty level. The problem is finding the right balance.

Also, the type of analysis required to solve the problem lends itself well to recursive solutions... perhaps build-in a (configurable) limit to how deep the analysis goes?

I am not sure how to apply this. My current expert solution is not recursive and I am not sure how I could stop it midstream. Did you have an implementation in mind?

If all else fails, or isn't enough, I am partial to my earlier suggestion - make the computer make mistakes! Randomly inject bad data into the algorithm in the form of bad or mis-spelled dictionary entries, randomly delete previously-guessed entries, etc...

As I indicated in my post, mistakes are factors that can be used in the difficulty factor. The problem is an actual implementation that results in a realistic player and not something too easy or too hard.