Your misconception has nothing to do with gravity - you're just getting a little mixed up about acceleration vs. relative acceleration.
Let's dispense with gravity, since it's a red herring here. Say there are two cars. Car A accelerates at $+3 ~\rm m/s/s$ (to the right). Car B accelerates at $-5 ~\rm m/s/s$ (that is, to the left). So far, so good, right? There's no paradox about two cars accelerating at different rates.
Now, suppose you are sitting in car B. If you want to measure the apparent, or relative, acceleration of car A relative to you, you just take the difference of the accelerations: $(3) - (-5) = 8 ~\rm m/s/s$. So car A is accelerating at $8 ~\rm m/s/s$ relative to car B.
If you're the driver of car A, and you want to measure the apparent acceleration of car B relative to you, you follow the same procedure: $(-5) - (3) = -8 ~\rm m/s/s$. So car B is accelerating at $-8 ~\rm m/s/s$ relative to car A.
That seems perfectly intuitive and contradiction-free to me. The magnitude of the relative acceleration of each car is equal, as it must be, since the relative acceleration of each car relative to the other represents the rate at which the separation distance is decreasing, which must be equal for both of them.
Going back to your example, the magnitude of the relative acceleration of the masses is $G M_a / r^2 + G M_b / r^2$†. Even though they have different accelerations in the frame of reference you chose at the beginning of the problem, their relative acceleration is the same.
† if you're wondering about the plus sign, consider that gravity produces accelerations in the two bodies that are opposite in direction, which we must represent by giving one of the two accelerations a negative sign. When we take the difference between the accelerations, that negative sign becomes a plus.
If you'd like a justification of the "take the difference of the acceleration" procedure, since it's the heart of my argument, here it is:
Let $x_a$ and $x_b$ be the positions of the two cars. The separation of the cars must be
$$s = x_a - x_b$$
If we want to know the rate of change of the separation of the cars, we can take the derivative of that equation:
$$\frac{ds}{dt} = \frac{dx_a}{dt} - \frac{dx_b}{dt}$$
If we take the derivative again, it should give us the rate of change of the rate of change of the separation, which is the relative acceleration:
$$\frac{d^2s}{dt^2} = \frac{d^2x_a}{dt^2} - \frac{d^2x_b}{dt^2}$$
The two quantities on the right side are simply the accelerations of two objects, $a_a$ and $a_b$, so
$$\frac{d^2s}{dt^2} = a_a - a_b$$