Coupon collector - the effect of randomization
$E[m]$ equals $n(H_n-1)$.  

Here's a more complete proof sketch, following the argument suggested in my comment.

We start by showing that each permutation of the first $k-1$ elements is equally likely.

More precisely, let $X^*=(X_1,X_2,\ldots,X_K, \ldots)$ be an infinite random sequence where each $X_i$ is drawn independently and uniformly from $S$.  Let r.v. $K$ be the first index at which all elements of $S$ have been seen. Let r.v. $X'=(X_1,X_2,\ldots,X_{K-1})$.

Let $i$ denote any positive integer. Let $s$ denote any element of $S$.
Let $x=(x_1,x_2,\ldots,x_{i-1})$ denote any value of $X'$ that can occur,
given that $K=i$ and $X_K = s$.  (That is, $x$ is any length-$(i-1)$ sequence in which
each element of $S-\{s\}$ occurs, and $s$ does not occur.)

Let $\pi$ be any permutation of $[i-1]$.
Let $\pi(x)$ denote sequence $x$, permuted by $\pi$.

Lemma: Fix any such $i$, $s$, $x$, and $\pi$. Conditioned on $K=i$ and $X_k=s$, the probability that $X' = x$ is the same as the probability that $X' = \pi(x)$.

Proof.  To save typing, let $(i,s)$ denote the event that $K=i\wedge X_K=s$.

We want to show $\Pr[X'=x ~|~ (i,s)] = \Pr[X'=\pi(x) ~|~ (i,s)]$.

Let $x\prec X^*$ denote that $x$ is a prefix of $X^*$. 
Let $x,s\prec X^*$ denote that $(x_1,\ldots,x_{i-1},s)$ is a prefix of $X^*$. 
Note that 
$$\Pr[X' = x ~|~ (i,s)]\,\Pr[(i,s)] ~=~ \Pr[X' = x \wedge (i,s)] ~=~ \Pr[x,s\prec X^*] ~=~ \frac{1}{n^i}.$$
Thus, 
$$\Pr[X' = x ~|~ (i,s)] ~=~ \frac{1}{n^i \Pr[(i,s)]}.$$
Since the right-hand side is independent of $x$,
and $\pi(x)$ is also a possible value of $X'$,
$\Pr[X' = \pi(x) ~|~ (i,s)]$ also equals the right-hand side above.  QED

Corollary: Randomly permuting the first $k-1$ elements of $X$
(as described in the question) does not change the distribution of $X$.

This implies that the distribution of the r.v. $m$ as defined in the question
(with permutation of the first $k-1$ elements)
is the same as the distribution of $m$ if the elements are not permuted.
That is, $m$ is distributed as the first index at which $n-1$ distinct
elements in $S$ have been seen.  By a standard calculation, 
$E[m]$ equals $n(H_{n}-1)$.