The user's solved the kata already.

Interesting solution. Shows that I need to have bigger tests. This is in no way optimal.

Note that you're looking for the shortest possible number of steps. Sure, you can revisit nodes, but if coin is going A to B to A to B a million times, will that sequence of moves likely be the minimum? Look for ways to limit your search space by leveraging this.

If I understand your approach, in a maze like this you may try every single path inside the top-right square before going back? Maybe even backtracking paths.

# ######
# #    #
# #    #
# #    #
# #    #
# ####^#
#      #
########

An improvement I could propose that comes from A-star algorithm without rewriting all yu've done entirel would be to attribute a "shortest distance to the start" score to nodes instead of some kind of recursive "who visited who" (I'm not sure I quite understand the visited part of your code though), then you only visit a node if its shortest registered distance to the start is bigger than its distance to the start in your path.

Of course that'd just be a patch, I think BFS approaches, from floodfill to A-star to Djikstra are always better than depth first when correctly implemented.

My game loop tests the map to see if any aliens can move

All aliens on the map can and will move forward 1 step. Depending on how you structure your data, it may make more sense to first spawn, then move.
Also, since aliens move before turrets fire, if an alien penetrates the base, it is effectively off the map.

Which language? I've solved this kata in several of them without using any sophisticated algorithm, just lightly template brute force, and the whole tests pass in less than 2 seconds.

As the author, I wouldn't rank this 7 kyu either. But as Kees de Vreudg already said: the ranking is community made, I don't have any influence to this ;)

It's not the author rating the Kata's.
Lately Kata's are tremendously underrated by a bunch of know-it-alls, who seem to call the shots here. You're better off focusing on the older ones.
That said: this one is actually not that difficult. I don't know why a straightforward solution is not working out for you.
I just solved this one in a few minutes, without any hocus pocus.

+1