Implications of non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials? In their seminal 1979 paper Representations of Coxeter groups and Hecke algebras (Invent. Math. 53, doi:10.1007/BF01390031),
Kazhdan and Lusztig studied an arbitrary Coxeter group $(W,S)$ and the corresponding Iwahori-Hecke algebra.   In particular they showed how to pass from a standard basis of this algebra to a more canonical basis, with the change of basis coefficients involving polynomials indexed by pairs of elements of $W$ (in the Bruhat ordering) over $\mathbb{Z}$.   Even though the evidence at the time was quite limited, they conjectured following the statement of their Theorem 1.1 that the coefficients of these polynomials should always be non-negative.  (In very special cases this is true because the coefficients give dimensions of certain cohomology groups.)
Several decades later, Wolfgang Soergel worked out a coherent strategy for proving the non-negativity conjecture, in his paper

*

*Kazhdan–Lusztig-Polynome und unzerlegbare Bimoduln über Polynomringen. J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525, doi:10.1017/S1474748007000023, arXiv:math/0403496
Now that his program seems to have been completed, it is natural to renew the question in the header:

What if any implications would the non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials have?

It has to be emphasized that in Soergel's formulation and the following work, the non-negativity is not itself the main objective.   Instead the combinatorial framework proposed was meant to provide a more self-contained conceptual setting for proof of the original Kazhdan-Lusztig conjecture on Verma module multipliities for a semisimple Lie algebra (soon a theorem) and further theorems in representation theory of a similar flavor.   But Coxeter groups form a vast general class of groups given by generators and relations, so it is surprising to encounter such strong constraints on the polynomials occurring in this generality.
ADDED: There is some overlap with older questions related to Soergel's approach, posted here and
here.
UPDATE: It's been pointed out to me that older work by Jim Carrell and Dale Peterson involves the non-negativity condition, though their main goal is the study of singularities of Schubert varieties in classical cases.   See the short account (with a long title)

*

*J.B. Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties.
Algebraic groups and their generalizations: classical methods (University Park, PA, 1991), 53–61, Proc. Sympos. Pure Math., 56, Part 1, Amer. Math. Soc., Providence, RI, 1994. https://doi.org/10.1090/pspum/056.1
The first section develops for an arbitrary Coxeter group some consequences of non-negativity of Kazhdan-Lusztig coefficients for the combinatorial study of Bruhat intervals.   For further details about the geometry, see

*

*Carrell, J., Kuttler, J. Smooth points of T-stable varieties in G/B and the Peterson map. Invent. math. 151, 353–379 (2003). https://doi.org/10.1007/s00222-002-0256-5, arXiv:math/0005025
I'm still not sure whether such consequences of the 1979 K-L conjecture are enough to make the conjecture in itself "important".    But it's definitely been challenging to approach.
 A: Non-negativity is important in the proof of Lusztig's 15 conjectures (in fact, it is easy to be proved with the non-negativity property, like in the "split case" and "quasi-split case"). Although even when in unequal parameter setting, where non-negativity is no longer true, we still can't find any counterexample of the 15 conjectures. When all the conjectures hold, a lot of work can be done on the representation of Coxeter groups and their Hecke algebras. Everything is contained here.  (I don't have enough reputation to add a comment, so I have to put my comment as an answer. I'm sorry if it is bad.)
A: Maybe I can provide a belated kind of answer to my own question, which I came across when looking for something else in the older literature.  Vinay Deodhar published a paper in 1990 here (just before family medical problems and then his own health prevented him from continuing his research).  This might have further combinatorial interest relative to Kazhdan-Lusztig polynomials for Coxeter groups outside the traditional framework of Lie theory.  But his approach depends crucially on the assumption that a given element of the Coxeter group is "good", which is implied by non-negativity of all coefficients in certain of the KL polynomials.    Deodhar seems to have expected, in line with the conjecture of Kazhdan and Lusztig, that this would always be satisfied.    
The impressive work of Elias and Williamson published in 2014 here extends earlier work of Soergel on his bimodules and thereby proves the non-negativity conjecture in general.   So Deodhar's algorithmic procedure might be worthwhile to revisit.   In any case, those who have access to Math Reviews should find it useful to track the reviews and later citations of both of these papers.
