First, just for clarifty about the question, the [Reifegerste preprint][Reif-arXiv] dates from September 2003, her [paper][Reif-art] was published in 2004, and Jacob Post's thesis is from 2009.

But the theorem is easy to show from things known well before that (basically what can be found in Knuth's treatment in The Art of Computer Programming), though I'm not sure I can point precisely to where what I will mention appears (first, explicitly). So while I don't know if anyone explicitly showed this differently _since_, I'll discuss how it could (and should) have been prove _before_.

First, the answer to your question 2 is that everything indeed goes through for words in place of permutations. The Schensted correspondence for words (in which the input is an arbitrary word, but not a sequence of bi-letters as in RSK; this version is already in the Schensted paper) commutes with standardisation more or less by definition: replacing a word by its standardisation (which is a permutation) changes its (semi-standard) $P$-tableau into its standardisation (now a standard tableau), while not affecting the $Q$-tableau (recording tableau) at all. Also standardisation maps Knuth-equivalent pairs of words to Knuth-equivalent pairs of permutations. However, there is not really any need for this reduction, because the argument is actually easier for the even more general case of the full RSK correspondence (even if the _statement_ is a bit more delicate: one applies a Knuth-equivalence involving the bottom entries of three consecutive bi-letters; then the $Q$-tableau changes by a permutation of two of the three of its entries corresponding to the top entries of those three bi-letters, where the definition of "corresponding" should be obvious, or can be avoided by assuming all top letters distinct).

Now for the first question, it is fairly obvious that a Knuth equivalence on positions $i-1,i,i+1$ will always affect the recording tableau by just some permutation of the entries $i-1,i,i+1$ (in the RSK version: a permutation of the top entries of the three consecutive bi-letters involved). The part of the recording tableau with strictly smaller entries records a part of the insertion process that does not yet involve any of the (bi-)letters affected by the Knuth-equivalence, so there is no change for entries${}<i-1$. Also, once those three consecutive letters have been inserted, the insertion tableaux ($P$) have become identical (again) because that is what Knuth-equivalence is about, and the recording tableaux have obtained the same shape (as$~P$); the remainder of the insertion process proceeds identically for both cases, so entries${}>i+1$ stay in place as well.

Now the main property of the RSK correspondence I will use is:

**Lemma**. _Suppressing the first bi-letter in a bi-word affects the recording tableau by removing the minimal (top-left) entry, and then rectifying the resulting skew tableau by jeu de taquin._

This is quite standard, but as often occurs it may be hard to point to a clear statement in the literature (I don't have TAOCP at hand right now to check). Certainly Knuth makes a statement saying essentially that row-insertion of a bi-word on one hand, and column-insertion of its bi-letters in reverse order on the other (which basically reverses the order used for the bottom values in the bi-word that also appear in the recording tableau), give the same $P$-tableau, and mutually Schützenberger-dual $Q$-tableaux. Suppressing the first bi-letter only removes the last step of reverse-column-insertion, and so leads to dropping the maximal entry of the Schützenberger-dual $Q$-tableau; by the definition of the Schützenberger-dual, this has on the non-dual $Q$-tableau the effect described in the lemma. (But this is probably more roundabout than necessary; I think the proof of the cited statement actually involves proving the lemma or something equivalent.) Maybe the symmetric form of the lemma is easier to understand: suppressing the bi-letter that is minimal in bottom-first lexicographic ordering (which gives the first occurrence of the minimal entry that is being inserted) affects the _insertion_ tableau by removing its top-left entry and rectifying.

Anyway, given the lemma we can reason as follows to prove the theorem. Let $(Q_0,Q'_0)$ be the recording tableaux of two bi-words related by an elementary Knuth equivalence; they are related by some permutation of the values that I will continue to call $i-1,i,i+1$. By successively suppressing all bi-letters that come before the triple where the elementary Knuth equivalence takes place, one gets pairs of recording tableaux $(Q_1,Q'_1),\ldots,(Q_{i-2},Q'_{i-2})$, the final pair corresponding to a case where the bi-letters involved in the Knuth equivalence come at are at the very beginning of the bi-word. By the lemma, $Q_k$ is obtained from $Q_{k-1}$ by suppressing the top-left entry and performing a jeu de taquin slide for $k=1,2,\ldots,i-2$, and a similar relation holds for $Q'_k$ and $Q'_{k-1}$. In the final pair $(Q_{i-2},Q'_{i-2})$ the entries $i-1,i,i+1$ are the three minimal ones, corresponding to the now initial bi-letters where the Knuth equivalence takes place; all higher entries occur in the same place in $Q_{i-2}$ as in $Q'_{i-2}$. From the cases allowed in a Knuth equivalence it follows that entries $i-1,i,i+1$ occupy a shape$~(2,1)$, with $i-1$ in the top left position, the entries $i,i+1$ interchanged in $Q'_{i-2}$ with respect to $Q_{i-2}$ (there had to be _some_ difference, since the $P$ tableaux are equal). This pair is related as described in case 1 of the question.

The jeu de taquin slide leading from $Q_{k-1}$ to $Q_k$ can be restricted to the entries $i-1,i,i+1$, and involves a jeu de taquin slide on that skew tableau of size$~3$ as well. In the backward direction, an outward jeu de taquin slide is applied to the size$~3$ skew tableau extracted from $Q_k$ to obtain the one extracted from $Q_{k-1}$. Since we know the tableaux extracted from $(Q_{i-2},Q'_{i-2})$ are related by case 1 it will suffice to show that, given two $3$-entry skew tableaux of the same shape, and related as described by one of the cases 1 and 2, if one applies a reverse (outward) jeu-de-taquin slide to each of them, into the same square, then the results will still be of the same shape (actually we know this already in the case at hand) and related by one of the cases 1 and 2. This is quite easy to show by considering the possible configurations; most of the time nothing important changes, but when the three squares fit into a $2\times2$ square and the slide is into the fourth of its squares, there is a transformation of case 1 into case 2; this is why case 2 is needed in the first place. The same considerations occur in a rather detailed proof I gave, in the context of discussing dual equivalence (which is the equality-of-shape-preserving part): proposition 2.3.2 in _The Littlewood-Richardson rule, and related combinatorics_, in Math. Soc. of Japan Memoirs 11, available from my [home page][home]. (This paper it is dated 2001, and its [arXiv version][LR] is from 1999.)

**Added** I finally came round to looking what Knuth says about this exactly. His 1970 paper (Pacific J. Math, 34(3)) mentions symmetry, but not reversal of the insertion order. Hower in The Art of Computer Programming Vol 3. (1975) one finds in section 5.1.4 the following

**Theorem C** (M.P. Schützenberger). _If $P$ is the tableau formed by the construction of Theorem A from the permutation $a_1~a_2~\ldots~a_n$, and if $a_i=\min\{ a_1~a_2,\ldots,a_n\}$, then Algorithm S changes $P$ into the tableau corresponding to $a_1~\ldots a_{i-1}~a_{i+1}\ldots~a_n$.

(_Proof_. See exercise 13, which naturally asks "Prove Theorem C".)

Here Theorem A states the Robinson-Schensted coreespondence for permutations, and Algorithm S (Delete corner element) is one step of evacuation. This is indeed the "symmetric form of the lemma" mentioned above.

  [Reif-arXiv]: http://arxiv.org/abs/math/0309266v1
  [Reif-art]: http://www.ams.org/mathscinet-getitem?mr=2061380
  [home]: http://www-math.univ-poitiers.fr/~maavl/
  [LR]: http://arxiv.org/abs/math/9908099