If Explore isn't working, my guess is it might have to do with the warp points on the map. I noticed that sometimes the AI path-finding gets confused by some maps depending on how the warp points are arranged.
Edit: Oh whoops. I was thinking of SE IV. I've no good guess about SE V.