This is another attempt to make a feasible approximation of this question. Two previous (unsuccessful) attempts are here.
Let $n\gg 1$ be a fixed number (say, $n=10^{10}$), $k\gg 1$ a natural number. Let $a,b$ be two permutations from $S_k$. Suppose that for every word $w(x,y)$ of length $\le n$, the permutation $w(a,b)$ has a fixed point. Is it true that every permutation in $\langle a, b\rangle$ has a fixed point?
If $k$ is allowed to be much, much larger than $n$, then no.
A consequence of the assumption is that $a$ and $b$ each have fixed points. Let's take a toy example and see for what $n$ the example works. Let $a$ be the cycle that moves the numbers 1 to 7 in an increasing fashion, and $b$ moves 6 to 10 in a decreasing fashion. Then this example works for $n=1$, and almost works for $n=2$. A word which may not have a fixed point is $ab^{-1}$.
That's ok. Let us copy the example above, and have $b$ move elements in an increasing fashion. Now the disjoint union will be an example for $n=2$. However, for any word, we can create a slice on which that word has a fixed point; taking thw disjoint union of enough examples (and enlarging the domains so that eventually there is a fixed-point free permutation generated by $a$ and $b$), we get an answer of no for very large $k$.
EDIT 2011.07.27
Since a conjugate of an element with a fixed point has a fixed point, I am going to attempt some optimization in my example. Let $W$ be the set of reduced group words of length at most $n$ on two variables (so there are about $4^n$ such words, most likely less). If $x$ is one of the variables and $w$ is a short enough word in $W$, then $xwx^[-1}$ may be in $W$; if it isn't, an equivalent reduced form is in $W$, so let us label this new form if needed $w'$, and say that $w$ and $w'$ are in the same conjugacy class. It should be clear that this relation can be extended to an equivalence relation on $W$. Further, when a word $w$ is realized in a permutation group $G$ by replacing the variables $x$ and $y$ by elements $a$ and $b$ from $G$, and we call the realization $v$, and similarly for $w'$ and $v'$, then $v$ has a fixed point iff $v'$ has a fixed point.
The upshot of the preceding paragraph is that I need worry only about distinct representatives of the equivalence relation for the construction, so let $C$ be a set of such representatives which has precisely one member from every equivalence class on $W$. Let the underlying set $X$ be $C \times 2n +1$. I will define the element $a$ to act on $X$ so that for all $c$ in $C$, $a((c,0)$ is $(c,0)$, $a((c,2n)) = (c,1)$, and otherwise $a((c, k))=(c,k+1)$. So $a$ looks like $C$-many copies of the cycle $(1,...,2n)$. I will define $b$ similarly, but with two key differences: $k > n$ will mean $b((c,k))=(c,k)$, and $k \leq n$ implies $j \leq n$, where $j$ is such that $b((c,k))=(c,j)$. So $b$ looks like $C$-many different slices acting in different ways on $(0,...,n)$
At this point, it should be clear that $ba^n$ will have no fixed points, because $a^n$ will have moved for each slice $(1,...n)$ "out of the reach of $b$', and we will arrange that $b$ moves each copy of $0$. I now want to ensure that for each $c$ in $C$, the realization of $c$ by $a$ and $b$ has a fixed point.
Choose a $c$ in $C$. If $c$ has only one variable, let $b$ act like $a$ does, except on this slice indexed by $c$ have $b$ look like the cycle $(0,...,n)$ where we had $a$ look like the cycle $(1,...,2n)$. Otherwise, $c$ has fewer than $n$ instances of both variables used to make words in $W$. Take the instances of one variable, say $x$, which will be replaced by $a$ in the realization of the word $c$, and divide $(1,...,n)$ into pieces to be acted on appropriately. If $x^k$ occurs in the word $c$ to the precise power $k$, we will need a piece of size $(k+1)$ consecutive integers inside $(1,...n)$. For illustration, assume the word $c$ is $x^2y^2x^{-2}y$ Let us reserve the pieces $(1,2,3)$ and $(5,6,7)$ in anticipation. $a^2$ will take 1 to 3 and $a^{-2}$ will take 7 to 5. Let us define $b$ to look like a cycle on $(0,..,n)$, with the proviso that it takes 3 to 4, 4 to 7 and 1 to 5. Otherwise make the choices consistent with the provisos. If I did not make a mistake, it should be clear that for this word $c$, its realization on this slice has 1 as a fixed point. So however the realization of $c$ might affect the other slices, it will have at least one fixed point on this slice.
This works for each word $c$ since we can use $c$ as a template to break $(1,..,n)$ into pieces on which $a$ will act in a predetermined fashion, but we can choose a fixed point and have enough freedom to choose $b$ to "stitch the pieces together" and still look like some cycle on $(0,...,n)$. I apologize for not having a more formal way to specify how $b$ acts on this slice. Alternatively, choose a small number $d(c)$ such that there are actions $a$ and $b$ in the symmetric group on $d$ letters where the realization of $c$ by $a$ and $b$ in this group has a fixed point, AND at the same time $ba^n$ does not have a fixed point; use that $d$ to replace my slice for $c$ above. I like my version because I can claim that $a and b$ are realizable by two members of the symmetric group on $m$ letters, where $m= 2n+1 \times$ cardinality of $C$.
I cannot be more clear or more concise right now. If this does not communicate the idea, I ask someone else to help Mark. END EDIT 2011.07.27
Gerhard "The Wheels Turn And Turn" Paseman, 2011.07.27
Let me have a go at this one. We want to show that for any finite set $W$ of reduced words in $a,b$, we can find a subgroup $G = \langle a,b \rangle$ of some symmetric group $S_k$ such that all words in $W$ have fixed points when evaluated in $G$, but $G$ contains fixed-point-free elements.
Suppose inductively that we can do this for some set $W$, and we want to extend the construction to $W \cup \{w \}$ for some new word $w$. We may suppose that $w$ is cyclically reduced and that $w$ acts fixed-point-freely in $G$.
If $w$ has length $n$, then we can define partial permutations $a,b$ in the obvious way on $n$ points such that $w$ fixes the first of these. For any $p>n$, it is then easy to extend these partial permutations to permutations of a set of size $p$ that generate a transitive subgroup of $S_p$. In fact, by an old theorem of Jordan, if a primitive permutation group of degree $p$ contains a $q$-cycle for some prime $q<p-2$, then it must be the alternating or symmetric group and, by choosing $p$ to be a sufficiently large prime, we can make $b$ contains such a cycle, and thereby ensure that $a,b$ generate $A_p$ or $S_p$.
Do this for some prime $p > k$ to give a group $H \le S_p$, and let $K < S_{k+p}$ be generated by the disjoint actions of $a$ and $b$ in $G$ and in $H$. So all elements of $W \cup \{w\}$ have fixed points in $K$ and it remains to show that $K$ contains fixed-point free elements.
If all relations in $a,b$ that hold in $G$ held in $H$, then $H$ would be a quotient group of $G$, which is impossible, because $|H|$ is divisible by $p$, but $|G|$ isn't. So the permutations generated by the relations of $G$ generate a nontrivial normal subgroup of $H$ which, by the simplicity of $A_p$, must contain $A_p$. So, there exists a relation $v$ of $G$ such that $vw$ acts fixed-point-freely in $H$. Since $w$ acts fixed-point-freely in $G$, $vw$ is a fixed-point-free elemtn of $K$ as required.
