Refactor visited nodes
Track visited nodes as a list instead of a dictionary (simpler, and since we only have 9 nodes there's not a large cost in iterating through them).  Avoid a global variable - they create strange bugs and are best avoided wherever possible.  We can concat to the list in the function call (avoiding .append() here as it would modify the list in place).
Generators, yay!
The recursive function now uses generators.  It also trys to traverse the graph and matches the built-up words against the dictionary, rather than trying to build all the permutations and search for each one. This should be a noticeable performance gain.  We can also remove permutation-creating function, since we're no longer using it.