Man, it's great how thorough the responses are here. Unfortunately, I don't think that I expressed myself clearly enough the first time. I'll take another shot at it (pardon the expression), and if it's still obscure I'll post a diagram. What I had in mind is:
Initially, let's say that instead of a gun, you have an impossibly long solid rod. If Venus is right on the horizon and you poke it with the rod, the end of the rod is outside of Earth's gravitational field. If Venus is rising at the time, the rod will alter it's angle relative to Earth and rise with it. If it's setting, the rod will follow and hit the Earth.
Now replace the rod with a laser. If you fire a pulse at Venus on the horizon, it will be on its way and hit where Venus was when it was fired.
Lastly, replace the laser with a
very high-velocity gun (say 90% of c). Would it not hit somewhere even farther away from Venus' current position, but still outside of Earth's influence? On the assumption that Venus is setting when it's fired, at some point on the lowering speed scale it would go into orbit, and even lower on the scale it would hit somewhere on Earth. If Venus is rising instead, then...

I just saw where I screwed up the rotation part of it. I was thinking of the trajectory as a solid line that follows the target, and of course it isn't. Anyhow, the escape velocity question is still what I was wondering about.