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.

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.