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.
Best Answer
I don't believe so. This is equivalent to computing the Kendall tau coefficient. There are a couple algorithms for doing this (one of which involves using a Merge sort to compute how many steps Bubble sort would take) but they are $O(n\cdot log\ n)$.