The Axiom of Choice implies that there exist infinite games in which neither player has a winning strategy. Thus, the Axiom of Choice is incompatible with the Axiom of Determinacy. An example of a game where neither player has a winning strategy is the following (caveat: I'm not a set-theorist).
The game is a subset $G \subset [0,1]$ of real numbers. At stage 1, player 1 chooses a bit which is either 0 or 1. At stage 2, player 2 (knowing player 1's choices so far) chooses another bit. The players then repeat. After $\omega$ steps, they have constructed a real number $g \in [0,1]$ where the odd bits of $g$ (in binary) are given by player 1's choices and the even bits of $g$ are given by player 2's choices. Player 1 wins if $g \in G$, and player 2 wins if $g \notin G$.
Regarding the question that inspired the question, I've had a look at the paper (it's available on Springerlink). I'm convinced that $L$ does have a winning strategy. So, that particular game is determined.