Thanks Bruce Westbury for reminding me that I wrote something about this in my younger days. Here's what I make of it today, which provides a "closed formula" of sorts, a bit along the line of Allen Knutson's answer.
I'll deviate from the OP in writing $\Lambda$ for the weight lattice, $\Lambda^+$ for the set of dominant weights, and $X^\lambda$ for the basis elements of $\mathbf{Z}[\Lambda]$ with $\lambda\in\Lambda$, I'll use the dot-action $w\cdot\lambda=w(\rho+\lambda)-\rho$ and a related operator $J:\mathbf{Z}[\Lambda]\to\mathbf{Z}[\Lambda]$ sending $P\mapsto\sum_{w\in W}(-1)^{l(w)}w(X^\rho P)X^{-\rho}$ in general, and in particular $X^\lambda\mapsto\sum_{w\in W}(-1)^{l(w)}X^{w\cdot\lambda}$. Weyl's character formula says that the character $\chi_\lambda$ of $V_\lambda$ satisfies
$$
\chi_\lambda.J(1)=J(X^\lambda)\quad\text{for all $\lambda\in\Lambda^+$}
$$
The left hand side is in fact also equal to $J(\chi_\lambda)$, since for any $P\in\mathbf{Z}[\Lambda]^W$ one has
$$
J(P)=\sum_{w\in W}(-1)^{l(w)}w(X^\rho P)X^{-\rho}
= P \sum_{w\in W}(-1)^{l(w)}w(X^\rho)X^{-\rho} = P.J(1),
$$
the second equality by $W$-invariance of $P$. Thus $\chi_\lambda$ and $X^\lambda$ have the same image by $J$.
Every $P\in\mathbf{Z}[\Lambda]$ is equivalent modulo $\ker(J)$ to a unique $P'\in\mathbf{Z}[\Lambda^+]$, i.e., a polynomial supported on the dominant weights. Concretely, define a $\mathbf{Z}$-linear operator $\alpha:\mathbf{Z}[\Lambda]\to\mathbf{Z}[\Lambda^+]$ by $\alpha(X^\mu)=0$ if $X^\mu\in\ker(J)$, which happens if $r\cdot\mu=\mu$ for some reflection $r\in W$, and otherwise $\alpha(X^\mu)=(-1)^{l(w)}X^{w\cdot\mu}$ where $w\in W$ is the unique element with $w\cdot\mu\in\Lambda^+$. Then $J(P)=J(\alpha(P))$ for all $P\in\mathbf{Z}[\Lambda]$. It follows from the above that $\alpha(\chi_\lambda)=X^\lambda$ for all $\lambda\in\Lambda^+$. In other words if $\chi:\mathbf{Z}[\Lambda^+]\to\mathbf{Z}[\Lambda]$ is the "character" map that linearly extends $X^\lambda\mapsto\chi_\lambda$, then $\alpha$ restricted to $\mathbf{Z}[\Lambda]^W$ defines the inverse "decomposition" map.
Now the decomposition of an orbit sum $m_\lambda=\sum_{\mu\in W(\lambda)}X^\mu$ is given by $\alpha(m_\lambda)=\sum_{\mu\in W(\lambda)}\alpha(X^\mu)$; since each $\mu$ gives at most one term, this shows that its decomposition involves at most as many irreducible factors as the size the $W$-orbit of $\lambda$.
If $\lambda$ is very large, it may be convenient to write $m_\lambda=\frac1s\sum_{w\in W}X^{w^{-1}(\lambda)}$ where $s$ is the size of the stabiliser in $W$ of $\lambda$, and using $\alpha(X^\mu)=\alpha((-1)^{l(w)}X^{w\cdot\mu})$ for any $\mu,w$, obtain
$$
\alpha(m_\lambda)
=\frac1s\alpha\left(\sum_{w\in W}(-1)^{l(w)}X^{w\cdot(w^{-1}(\lambda))}\right)
=\frac1s\alpha(X^\lambda J(1)).
$$
If $\lambda$ is strictly dominant one has $s=1$, and if moreover $\lambda$ is far enough off the walls that $X^\lambda J(1)$ is entirely supported on dominant weights, then the right hand side simply becomes $X^\lambda J(1)$, which has $|W|$ distinct terms.
This coincides with the expression that Allen Knutson guessed. However the requirement is rather stronger than he suggested: in type $A_n$ for instance, dominant weights can be represented by weakly decreasing $n+1$-tuples of integers, with $\rho=(n,n-1,\ldots,1,0)$, and the "off the walls" condition means that the successive entries for $\lambda$ decrease by at least $n+1$. In other words, in this case the simplified formula holds only if $\lambda-(n+1)\rho$ is dominant.
