The inversion is conveniently described in terms of the Fourier transform $$g(x,p)=\int dy\,e^{-iyp}G(x+y/2,x-y/2).$$ Then the composition $f(x,p)=g(x,p)\star h(x,p)$ is a matrix multiplication [1], $$F(x,y)=\int dz\, G(x,z)H(z,y).\qquad(\ast)$$ So to find $h$ if $f$ and $g$ are given one would first calculate the Fourier transforms $F$ and $G$, $$G(x+y/2,x-y/2)=\frac{1}{2\pi}\int dp\,e^{iyp}g(x,p),$$ then solve the integral equation $(\ast)$ for $G$, and finally transform back to $g$. Whether this is doable will of course entirely depend on the details of the particular problem. But this is the general recipe.
[1] Map of Witten's $\star$ to Moyal's $\star$, Itzhak Bars, 2001.