This is the culmination of about 11 years of research but after I discovered it I found a proof that was extremely trivial, so I'm wondering if it's already known.
Let $(a,b)$ with $a < b$ positive integers denote the transpositions in the symmetric group. Turn them into a vector space with the relation $$(a,b)+(b,c)=(a,c)$$ (This is the root system thinly disguised.) Let $F$ be the tensor algebra on this vector space. For an element $w\in S_{\infty}$ define $$T_w = \sum_{\substack{(a_1,b_1)\cdots (a_n,b_n) = w\\\ell((a_1,b_1)\cdots (a_i,b_i))=i}} (a_1,b_1)\cdots (a_n,b_n)$$ Then the elements $T_w$ are linearly independent. Define $$T_{w/u} = \sum_{\substack{u(a_1,b_1)\cdots (a_m,b_m) = w\\\ell(u(a_1,b_1)\cdots (a_i,b_i))=\ell(u)+i}} (a_1,b_1)\cdots (a_m,b_m)$$ Then $$T_{w/u}=\sum_{v}{c_{u,v}^wT_v}$$ where $c_{u,v}^w$ is the structure constant in the cohomology ring of the complete flag variety.
So the question is: is this already known?