(in contrary to what I thought in my comment,) here is a proof that the exchange condition holds:

Let $(W,S)$ be a Coxeter system, $Q \in S^*$ a word in $S$, $w \in W$, $P$ a subword of $Q$ (given by the positions of its letters), and $(Q,w,P)$ be the set of subwords $X$ of $Q \setminus P$ such that the complement $R = Q \setminus X$ has greedy product $Dem(R) = w$ and the skips in the greedy product are in exactly the positions in $P$.
Let $D(Q,w,P)$ be the simplicial complex with facets given by $(Q,w,P)$ and observe that it is clearly a pure complex.

I believe I can show that $D(Q,w,P)$ is vertex-decomposable by showing that the deletion and the link of the first letter in $Q$ are again complexes of the same form. The argument is almost the same as in Allen and Ezra's mentioned paper.

The crucial step is the following (which is indeed depending on some notions we recently introduced, but which are still fairly elementary):


Let $q$ be the first letter in $Q$ and let $Q' = Q \setminus q$, and we assume that $q$ is a left descent of $w$ (this is, there is a word for $w$ that starts with $q$).
Then we have to show the exchange condition.
This is, we have to show that if there is for any facet $X$ of $D(Q,w,P)$ such that this first letter $q$ is in $X$,there is a facet $Y$ of $D(Q,w,P)$ such that $q$ is in the symmetric difference of $X$ and $Y$.
In other words, there must be a facet $Y$ that contains all letters of $X$ except this initial $q$.

The point is that this $Y$ exists in the complex $D(Q,w,\{\})$ because of the exchange condition in $(W,S)$.
But the "flip" from $X$ to $Y$ in $D(Q,w,\{\})$ changes the root configuration as described in Lemma 3.3(3) in my paper http://arxiv.org/abs/1111.3349 with Vincent Pilaud.
Therefore the root configuration gets changed by applying the simple generator $q \in W$ to all entries in the root configuration between the first position and the position of the unique letter in $Y \setminus X$.
But this simple generator cannot change the sign of any root in the root configuration except of the simple root $\alpha_q$.
But the simple root $\alpha_q$ can only appear with a negative sign in the root configuration *after* the position of the letter in $Y\setminus X$
Finally, we conclude that $Y$ is also a facet of $D(Q,w,P)$ using item 1 in my lengthy comment-as-an-answer.

(I have to run now and will add some details tomorrow. I hope this is already somewhat clear -- sorry for being sloppy!)