How is the conservation of momentum satisfied in long-range attraction such as electromagnetism and gravity?

I'm not a physicist, but my understanding is that electromagnetism (including attraction between opposite charges) is mediated by the photon, and gravity is probably (hypothetized to be?) mediated by the graviton.

I'm curious how that works from the point of view of the conservation of momentum. My naive imagination is, if a particle leaves A to the direction of B, doesn't that mean that A would have to change its momentum to the other direction (away from B)? And when B absorb this particle coming from A, shouldn't B now change its momentum to the same direction (away from A)?

How come is it that in the case of gravity and electromagnetism, A and B move towards each other as a result of this interaction?

Answer

If you consider things classically (for the moment forgetting about virtual particles as mediators of the force) things get more clear.

For instantaneous forces (which do not exist in nature), momentum conservation comes from the fact, that the forces in nature fulfil Newtons axiom actio = reactio, meaning, that for two particles, that interact we have the equations of motion:

$$m_x \ddot x = F(x, y)$$ $$m_y \ddot y = -F(x, y)$$

For the time derivative of the total momentum we get:

$$\partial_t P = \partial_t (p_x + p_y) = \partial_t (m_x \dot x + m_y \dot y) = m_x \ddot x + m_y \ddot y = F(x, y) - F(x, y) = 0$$.

That is the total momentum is conserved.

If we consider that the fields causing the forces propagate (and thus the forces are not instantaneous) we have to consider the momentum of the fields and can write local equations for momentum conservation.

Now: Do not take the virtual particle thing too serious. They are in many ways just mathematical artefacts of how we compute things in quantum field theory (so called perturbation theory). Most importantly, do not confuse them with some macroscopic particle. Rather they are "packets" of waves. Furthermore each elementary process conserves momentum (techspeak: the momentum is conserved at all vertices of a Feynman diagram)! As they are a computational device, the virtual particles do not follow the usual rules of propagating particles, but even if a virtual particle starts from A with a moment away from the particle B, it still can reach B and there interact and give B the momentum carried away from A (thus conserving the total momentum).