I have been doing refining and I have somewhat solved my question. As Raymond Hettinger said, the exhausted generator is returned when the same arguments are passed. However, this is nice because is prevents the function from returning already calculated values. Additionally, I added a yeild from which was the missing piece I needed to make this all work.

Below is the refreshed code:

from functools import lru_cache
import networkx as nx
import numpy as np
from itertools import combinations

@lru_cache(maxsize=None)
def iter_node_2(
        t_matrix: tuple[tuple], 
        must_retain_nodes: tuple, 
        removed_nodes: tuple, ):
    # Since NDArrays are not hashable I bring in the array as a tuple
    matrix = np.array(t_matrix)
    G = nx.from_numpy_array(matrix)
    for node in removed_nodes:
        G.remove_node(node)
    for node in G.nodes:
        if node not in must_retain_nodes:
            g_t = G.copy()
            g_t.remove_node(node)
            # check that every vertex that we care about is connected
            if all([nx.has_path(g_t, *a) for a in combinations(must_retain_nodes,2)]):
                new_removed_nodes = [*removed_nodes, node]
                # sort the tuple to avoid different permutations of the same node
                new_removed_nodes.sort() 
                yield from iter_node_2(t_matrix, must_retain_nodes, tuple(new_removed_nodes)
                yield new_removed_nodes


matrix = np.array([
    [0,0,1,0,1,],
    [0,0,0,1,1,],
    [1,0,0,1,0,],
    [0,1,1,0,0,],
    [1,1,0,0,0,],
])
must_retain_nodes = (0,1)
hashable_matrix = tuple((tuple(a) for a in matrix))
solutions = list(iter_node_2(
    hashable_matrix,
    must_retain_nodes,
    (),
))
print(solutions)

# should return: [[2], [2, 3], [3], [4]]