There are a lot of good and a few incorrect responses here. As an engineer, I figure I should at least weigh in with a few technical observations about the issue itself and the comments that have been provided.
Yes, the rifle moves well before the bullet exits the barrel. In fact, it is physically impossible to stop the rifle from moving before the bullet exits the barrel. To emphasize this point, the rifle will recoil and move even if the butt is placed up against a concrete barrier - in this case most of the movement will be in the form of spring compression in the stock, but it WILL move. In fact, even an infinitely stiff rifle will move the concrete before the bullet leaves the barrel - all in proportion to the mass ratio. It's all physics.
Rifle movement and Rifle Recoil both begin the moment the sear starts dropping. As someone correctly pointed out earlier, the rifle actually accellerates rearward as the firing pin moves forward, forward when the pin hits the primer, and then rearward again as the bullet starts to accelerate down the barrel. The first two movements are minor, and the latter is major but not so simple.
Although its easy to assume that the biggest POI influence is the recoil itself, it really isn't! PERFECT recoil (straight rearward in reaction to the bullets movement straight forward) only adds a minor negative component to the bullets forward velocity. It's the other movements, mostly caused by the recoil, that result in the most significant poi changes. The most important of these is the displacement of the barrel's muzzle caused by reactive forces in the stock, rest, shooter's shoulder and hand, and by various rifle components. As someone else pointed out, even barrel twisting caused by the bullet's rotational accelleration has some influence. In fact, it is important to realize that barrel vibration (all vibrations are movements) is one of the key reasons for doing nodal accuracy development. But that's a whole nuther discussion.
Does recoil influence POI? ABSOLUTELY IT DOES! Not minimally either! Even small calibers are influenced by it, but the bigger the caliber the bigger the effect. As someone else said, try shooting with a hand on the scope pushing down vs none, or try shooting with a firm hold vs no hold, or with shoulder pressure and without, or as the OP already noted - using different rest types.... These are all evidence that recoil influences poi through the OTHER forces and resulting movements that the recoil forces generate.
Am I surprised by the magnitude of the changes that the OP experienced? Not in the least! Using simple trigonometry, a 6 MOA poi shift is only 40 thousands displacement in the line of the bore at the muzzle vs the line of sight when the trigger was pulled. In reality, trigonometry significantly understates the effect because muzzle displacement is not linear. However, it is sufficient to illustrate the point. Just 40 thou of muzzle displacement is more than enough to put a bullet 6 MOA off course. 40 thou might seem like a lot to some, but if that's all a muzzle ever moved, most shooters probably wouldn't see or notice it because it's so small compared to the rearward recoil movement that they both see and feel.
Hope that helps