How do the Catalan numbers turn up here?

Your suspicions are correct. Let's show that a permutation is lucky iff it avoids the pattern 312.

For an injection $W$ from $\{1,\ldots,k\}$ to $\{n-k+1,\ldots,n\}$, let $N(W)$ denote the result of removing $W(1)$ and increasing all elements below $W(1)$ by $1$. For example, $N(32514) = N(3524)$.

Lemma 1. If $W$ avoids $312$ then so does $N(W)$.

Proof. Clear since the relative order of elements in $N(W)$ is the same as the corresponding elements in $W$.

Lemma 2. Suppose $W$ avoids $312$. After running one round of the algorithm, $S(1)$ contains the index of the minimal element in $W$, and $W \circ S = N(W)$.

Proof. The lemma is clear if $W(1)$ is the minimal element. Otherwise, since $W$ avoids $312$, all elements below $W(1)$ form a decreasing sequence $W(1) = W(i_1) > \cdots > W(i_k)$. The algorithm puts the minimal one $W(i_k)$ at $S(1)$, and puts $W(i_t)$ at $W(i_{t+1})$.

Theorem 1. If $W$ avoids $312$ then $W$ is lucky.

Proof. Apply Lemma 2 repeatedly. Lemma 1 ensures that the injection always avoids $312$.

For the other direction, we need to be slightly more careful.

Lemma 3. If $W$ contains a pattern $312$ in which $3$ doesn't correspond to $W(1)$ then $N(W)$ contains a pattern $312$.

Proof. The pattern survives in $N(W)$ since all relative positions are maintained.

Lemma 4. If $W$ doesn't contain a pattern $312$ in which $3$ corresponds to $W(1)$ and $1$ corresponds to the minimum of $W$ then after running one round of the algorithm, $S(1)$ contains the index of the minimal element, and $W \circ S = N(W)$.

Proof. Follows directly from the proof of Lemma 2.

Thus we should expect trouble if there are $i<j$ such that $W(1) > W(j) > W(i)$. However, if $W(i)$ is not the minimal element, the trouble won't be immediate.

List the elements which are smaller than $W(1)$ as $W(t_1),\ldots,W(t_k)$, and suppose that $W(t_r) < W(t_{r+1}) > \cdots > W(t_k)$. One round of the algorithm puts $t_r$ at the place of $t_{r+1}$. The following rounds maintain the relative order of the elements in positions $t_{r+1},\ldots,t_k$, and so in the final result, the position which should have contained $t_{r+1}$ will contain $t_r$.

Example: $W = 632541$. The final result is $S = 652134$, which corresponds to the permutation $143625$. We can see that $S(1)$ is correct since $W$ satisfies the conditions of Lemma 4. We have $t_r = 3$ and $W(t_r) = 2, W(t_{r+1}) = 5$. We see that indeed $W(S(5)) = 2$ instead of $5$.

Theorem 2. If $W$ contains $312$ then $W$ is unlucky.

Proof. Along the lines of the discussion above.

I think that your program is doing something very similar to a simple stack sort. I found this paper online http://www.combinatorics.org/Volume_9/PDF/v9i2a1.pdf which explains both the basic stack sort and some variations. In the case of the basic stack sort, Donald Knuth has proved that the number of sortable permutations of length n is $C_n$ (this is proposition 1.3 in the linked paper).

Your method does not replicate stack sort exactly, but I think it will output a cyclically shifted version of what the stack sort algorithm will produce. I'll edit my answer if I figure out some more details.