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).$$ So to find $h(x,p)$ if $f(x,p)$ and $g(x,p)$ are given one would first calculate the Fourier transform $F(x,y)$ and $G(x,y)$, then solve this integral equation for $G(x,y)$, and finally transform back to $g(x,y)$. 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.