Okay, taking a second stab at this. Same overall technique, hopefully I can count better this time.
We start with our root node, labeled '1'. We add nodes 2 through k in succession. The labels are intended to correspond to the order in which we choose them when running the algorithm. The leaves of the tree are the nodes which are "dead". We can attach each node to any of the nodes we have already placed, leading us to the conclusion that we have $(k-1)!$ labeled $k$-node trees where each node's parent has a smaller label than the node does. We will associate each tree with the sequence of parents $\{ 1 =p(2), p(3), ... p(k) \}$ where $p(j) \in [1,...,j-1]$.
We are then going to add nodes and edges to complete this to a graph $G$ that can give this tree as a result of the algorithm above. For the $(n-k)$ nodes that are not in the tree, we label them (all labelings are equivalent at this point), then we can connect them to the leaves of the tree and we can connect them to each other, leading to $e_1(l;n-k) = (n-k)*l + (n-k)C2$ possible edges for $l$ leaves.
Now to count within-tree edges. A node $i$ can be connected to a node $j+1 > i$ in the graph $G$ if one of three (mutually exclusive) conditions holds: 1) $i$ is the parent of $j+1$ in the tree ($i=p(j+1)$), 2) $i$ is greater than $p(j+1)$, or 3) $i$ is a leaf and $i$ is less than $p(j+1)$.
This is very difficult to count. It is best to note, however, that the within-tree edges are independent of $n$, and so we can count them once for any given tree.
Let $T_k$ be the set of labeled $k$-node trees as above and $T_{k,l}$ be the set of labeled $k$-node trees with $l$ leaves. Given a tree $t$ in $T_{k,l}$, let $e(t)$ be the number of edges one can add to $t$ consistent with $t$ being a potential outcome of the algorithm run on the resulting $k$-node graph. We note that since one may freely connect each leaf to every other leaf, $e(t) \geq lC2$. We will then define a polynomial
$t_k(x) = \sum_{l=1}^{k-1} \left( \sum_{t \in T_{k,l}} 2^{e(t)} \right) x^l$.
The coefficient of $x^l$ is the number of ways one may complete $k$-node, $l$-leaf trees to a $k$-node graph consonant with the algorithm. By definition, this coefficient is divisible by $2^{lC2}$.
The first few $t_k(x)$ are as follows (I think):
$\begin{array}{c} t_2(x) = x \\ t_3(x) = x + 2x^2 \\ t_4(x) = x + 14x^2 + 8x^3 \\ t_5(x) = x + 70x^2 + 264x^3 + 64x^4 \end{array}$
It is not immediately obvious that there is a recursion relation for these polynomials. One might hope that since adding a node to a $k$-node, $l$-leaf tree gives either a $(k+1)$-node, $l$-leaf tree or a $(k+1)$-node, $(l+1)$-leaf tree, that one could find a recursion relation for $[x^{l+1}]$ in $t_{k+1}(x)$ in terms of $[x^l]$ and $[x^{l+1}]$ in $t_k(x)$. I have not yet found such a relation.
Why do we care about these polynomials in the first place? It's fairly simple: given the dependence of $e_1(l;n-k)$ on $l$, the number of ways to complete $k$-node trees to an $n$-node graph is $2^{(n-k)C2} * t_k(2^{n-k})$. To get the number of ways to run the algorithm on the set of $n$-node graphs, one simply sums this quantity over $k$. And of course, the number of algorithm runs that result in a spanning tree is $t_n(1)$.
Update: I believe I have found a recursion for the coefficients of $t_k(x)$. I do not yet have the coefficients in closed form. This recursion requires us to divide up the set $T_{k,l}$ of $k$-node, $l$-leaf trees further.
For a given $(k+1)$-node, $(l+1)$ leaf tree $t$, we will consider the last non-leaf node (say it has label $a$), and any leaf of said non-leaf node (say it has label $b$). We then remove said leaf, and decrement the labels of all the later leaves. The resulting tree, t', has $k$ nodes and either $l$ or $l+1$ leaves, depending on whether $a$ had more than one leaf in $t$. This map is not a function, as we can choose $b$ arbitrarily if $a$ has more than one node, but for now we will pretend it is a function. We will call this map $f: T_{k+1,l+1} \rightarrow T_{k,l} \cup T_{k,l+1}$.
If $a$ had more than one leaf in $t$, we find that e(t) = e(t') + l. If $a$ only had $b$ as a leaf in $t$ (so that $a$ itself is a leaf in $t'$), then we find that e(t) = e(t') - (k-a) + l. These equations are not difficult to verify.
We now divide up our set $T_{k,l}$ into sets $T_{k,l,m,q}$, where $k$ is the number of nodes in the tree, $l$ is the number of leaves, $m$ is the label of the last non-leaf node and $q$ is the number of leaves on node $m$. We let
c_{k,l,m,q} = \sum_{t' \in T_{k,l,m,q}} 2^{e(t')}
be the number of ways to reconstruct a $k$-node graph from trees in $T_{k,l,m,q}$.
We are now going to attempt to invert $f$ on $T_{k,l,m,q}$. We can either add a leaf to the non-leaf node $m$, giving a tree $t$ in $T_{k+1,l+1,m,q+1}$, or we can add a leaf to a leaf node m' > m, giving a tree $t$ in T_{k+1,l,m',1}. In each case, we need to consider what label we are going to assign to the new leaf (and we increment all the labels after the new label), and how $e(t)$ is related to e(t').
In the latter case, e(t) = e(t') - (k-m') + l and we have (k+1-m') choices for the label of the new leaf. In the former case, e(t) = e(t') + l, and we have $(k+1-m)$ choices for the label of the new leaf. We point out that in this case, every tree $t$ in $T_{k+1,l+1,m,q+1}$ has $(q+1)$ not-necessarily-distinct images t' under $f$, but all have the same value of e(t') (this last fact is not too difficult to prove).
We therefore find the following recurrences:
c_{k+1,l,m',1} = (k+1-m') * 2^{l +m' - k} \sum_{m
$c_{k+1,l+1,m,q+1} = \frac{k+1-m}{q+1} * 2^l c_{k,l,m,q} $.
Boundary conditions on these recurrences are as follows:
$c_{k,l,m,q} = 0$ if $l\geq k$ or $q>l$ or $m+q>k$
$c_{l+1,l,1,l} = 2^{lC2} $
The coefficients of the polynomial $t_k(x)$ are $[x^l] = \sum_{m,q} c_{k,l,m,q}$.