Error with optimality in Iterative Deepening Depth First Search algorithm

I have implemented a version of Rush Hour (the puzzle board game) in Python as a demonstration of some AI algorithms. The game isn't important, because the AI is relatively independent of its details: I've attempted to implement a version of iterative deepening depth first search in Python as follows (note that this code is almost directly copied from Russell and Norvig's AI text, 3rd edition, for those of you who know it):

def depth_limited_search(game, limit):
    node = GameNode(game)
    frontier = []
    #frontier = Queue.Queue()
    frontier.append(node)
    #frontier.put(node)
    frontier_hash_set = set()
    frontier_hash_set.add(str(node.state))
    explored = set()
    cutoff = False
    while True:
        if len(frontier) == 0:
        #if frontier.empty():
           break
        node = frontier.pop()
        #node = frontier.get()
        frontier_hash_set.remove(str(node.state))
        explored.add(str(node.state))
        if node.cost > limit:
            cutoff = True
        else:
            for action in node.state.get_actions():
                child = node.result(action)
                if str(child.state) not in frontier_hash_set and str(child.state) not in explored:
                    if child.goal_test():
                        show_solution(child)
                        return child.cost
                    frontier.append(child)
                    #frontier.put(child)
                    frontier_hash_set.add(str(child.state))
    if cutoff:
        return 'Cutoff'
    else:
        return None

def iterative_deepening_search(game):
    depth = 0
    while True:
        result = depth_limited_search(game, depth)
        if result != 'Cutoff':
            return result
        depth += 1

The search algorithm, as implemented, does return an answer in a reasonable amount of time. The problem is that the answer is non-optimal. My test board of choice has an optimal answer in 8 moves, however this algorithm returns one using 10 moves. If i replace the lines above commented out lines with the commented lines, effectively turning the iterative deepening depth-first search into an iterative deepening breadth-first search, the algorithm DOES return optimal answers!

I've been staring at this for a long time now trying to figure out how a simple change in traversal order could result in nonoptimality, and I'm unable to figure it out. Any help pointing out my stupid error would be greatly appreciated