How was this Mersenne Twister seed for a 20-character string known a priori found?
How did he do this?


Actually, you gave much of it away when you mentioned:


  You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.


This is true, but you can do other things with it.  You can also generate previous output (that is, what the Mersenne twister output would be on blocks previous to the one you saw),previous states (that is, what the twister state had to be so that, after an iteration of the twister, you would get the selected state) and also compute the necessary seed to obtain a specific state.

Hence, most likely here's what he did:


Created an output of 624 integers, which consisted of the "9!dlroW ,olleH"ck,@ (which is 20 bytes or 5 integers), along with 619 arbitrary values.  These last 619 integers will be ignored, and hence it doesn't matter what values you select for them.
Reconstructed the internal twister state needed to generate this output.
Generated the previous twister state needed to generate this state after going through the twister permutation
Generated the seed needed to generate this twister state


And that's it.  The above is a bit tedious to do by hand; it'd be fairly trivial for a program.