Making an assumption that the mass of the gun ($M$) is much greater than that of the bullet ($m$) , the net force on the bullet is: (From the gun's frame.)
$$m \frac{d^2r}{dt^2}=mv\frac{dv}{dr}=-\frac{GMm}{r^2}$$
The equality is obtained from the fact that acceleration is $\frac{dv}{dt}$, which equals $\frac{dv}{dr}\frac{dr}{dt}$, (via the chain rule) the second term being the velocity.
After integrating this, we get:
$$\frac {mv^2}{2}-\frac{GMm}{r}=c$$
If we assume that the bullet stops at an infinite distance (i.e, it escapes the gun, never to return), its energy at that time would be zero.
From this, we get:
$$v_i=\sqrt\frac{2GM}{r}$$ (where $r$ is the distance from the center of mass of the gun to the point where it left the gun.)
This is the escape velocity of the bullet. (like @Jonas and @Steven Mathey and @John Duffield have mentioned.)
For all initial velocities greater than this, the gravitational force from the gun would be unable to draw the bullet back. Considering how small the value of $v_i$ generally is compared to average bullet speeds, the bullet mostly will escape.
(The initial assumption helps make the math easier, but it is not an absurd assumption. This assumption is the mathematical equivalent of saying that the gun would not move at all because of the force exerted by the bullet on it.)