Lets given a finite set (called an alphabet) $\Sigma$ and consider the set of first order formulas with atomic formulas $$ = , \quad < , \quad R_a \quad (a \in \Sigma). $$ For a given word $w \in \Sigma^{\ast}$ (i.e. a sequence with letters from $\Sigma$), the interpretation is as follows: We set $\mbox{Dom}(w) = \{1,\ldots, |w|\}$ and $R_a := \{ i \in \mbox{Dom}(w) \mid w_i = a \}$, and $=, < $ are interpreted as usual. Hence the variables are the positions in the word, and the predicates are for determining what letter we have at a specific position.
Example: Let $w = ababa$ with $\Sigma = \{a,b\}$. Then $\mbox{Dom}(w) = \{1,2,3,4,5\}$ and $R_a = \{1,3,5\}$, $R_b = \{2,4\}$. Hence the sentence $$ \forall x ( R_b(x) \rightarrow \exists y ( R_a(y) \land y > x ) ) $$ is satisfied by $w$, whereas $\forall x ( R_a(x) )$ is not satisfied.
An Ehrenfeucht-Fraisse-Game between two Players Player I and Player II on two words $u, v$ with $p \ge 0$ turns is played according to the following rules: Player I starts, he chooses some word and marks an arbitrary position in it, then Player II takes turn and marks a position in the other word. This procedure goes on for $p$ turn, after which both players have marked $p$ position (where a position could be marked multiple times).
The markings are then interpreted as assignments of positions to variables $x_1, x_2, \ldots, x_p$ for the word choosen by each player. For example, if we have $u = ab, v = baa$, Player I chooses $v$ and marks the first $a$, then Player II marks the first $a$ in $u$, then Player I marks the second $a$ in $v$ and then Player I the first $a$ in $u$, we have for $u$ the variable assignment $x_1 = x_2 = 1$ and for $v$ we have $x_1 = 2, x_2 = 3$.
Player II wins, iff with this assignment, every atomic formula over $\{x_1, \ldots, x_p\}$ which is true for $u$ is also true for $v$ and vice versa.
In the above example, Player I wins, as the formula $x_1 < x_2$ is true on $v$ but not on $u$ with the given assignments (but $R_a(x_1), R_a(x_2)$ are both true).
Now, a fundamental theorem for such Ehrenfeucht-Fraisse-Games is:
Player II has a winning strategy in the above given with $p$ turns iff no formula with $p$ variables and quantifier depth at most $p$ distinguishes both words.
So, for example consider $$ u = ababab, \quad v = bababa. $$ Then the first order formula $$ \exists x \forall y ( ( x < y \lor x = y ) \land R_a(x) ) $$ is true on $u$, but not on $v$, hence a formula of quantifier depth two can "separate" both words. But I can find no winning way for Player I with two turns. More, I think this is not possible, i.e. Player II has a winning strategy. For by symmetry suppose Player I chooses $u$ and marks some position with symbol $x \in \{a,b\}$. Then Player II chooses a position in the middle of $v$ with the same symbol $x$. Then its Player I's turn again, and if he chooses a position greater than the previously choosen one, Player II is free to choose one that is greater too with the same symbol, and if Player I choose a smaller position Player II can react in the same way (same if Player I chooses the same position in the second turn). Hence after two moves all formulas of the form $x_1 < x_2$, $R_a(x_2)$ etc are fullfilled on both words? So, this contradicts the fundamental theorem about Ehrenfeucht-Fraisse-Games.
What am I missing, does anybody sees where my reasoning breaks down?
What you're missing is that Player I can play in different structures on different turns. In fact, in general, if a sentence $\varphi$ separates structures $M$ and $N$, each alternation of quantifier type in $\varphi$ corresponds to a switch of which structure Player I plays in, in the winning strategy corresponding to $\varphi$.
Here's the winning strategy for Player I in your example.