Why isn't electromagnetism incompatible with special relativity? The notion that newtonian gravity is incompatible with special relativity is often suggested by declaring the familiar equation $$F_g=\frac{Gm_1m_2}{|\vec{r}_1(t)-\vec{r}_2(t)|^2}$$ and stating that this requires the notion of both particles instantaneously being at certain positions, which doesn't hold up when you allow moving observers to measure time differently.
It is often said that electromagnetism (in the form described by Maxwell's equations) is compatible with special relativity since the equations are symmetric under a Lorentz boost; there exists a reformulation of Maxwell's equations in terms of the field tensor $F_{\mu\nu}$ and the 4-current $(\rho,\vec{J})$. However, we can use Maxwell's equations and the Lorentz force law to find an expression very familiar to the one mentioned above: $$F_e=\frac{k_eq_1q_2}{|\vec{r}_1(t)-\vec{r}_2(t)|^2}.$$
Why doesn't the same special relativity-based objection apply to this equation?

A common answer seems to be that the form of Coulomb's law written above is only valid for static cases. I don't believe that's correct: Coulomb's law accurately describes the electric attraction/repulsion even in a non-relativistic approximation if the charges are moving (or at the minimum, it is mathematically well-defined because a universal time is defined); to find the actual net force, one would simply need to add a magnetic correction, in accordance with the complete Lorentz force equation. I understand that once you do that, you're involving relativity under the hood, even though it looks newtonian, but if that's the case, why can't the Newtonian gravitational force expression be similarly modified using a similar velocity-dependent "correction"?
 A: Probably because the Maxwell equation you furnish holds only if the charges are not moving relative to one another. If they are, then magnetic forces will come into play and the situation gets more complicated.
My way of looking at this is as follows: Maxwell's equations can be used to derive the speed of electromagnetic interactions, and we find this answer does not contain any dependence on the relative motion of the source and the detector. In this sense, Maxwell's equations contain special relativity.
However, the speed with which gravitational interactions are propagated through space (i.e., c) is not extractable from Newton's law of gravity. This means there are truths contained in GR which Newton's gravity cannot furnish us, and hence that Newtonian gravity is incomplete.
A: 
Why doesn't the same special relativity-based objection apply to this equation?

The same objection doesn’t apply because this formula (Coulomb’s law) is only valid in static situations. The simultaneity issues you mention do not arise in a static scenario.

we can use Maxwell's equations and the Lorentz force law to find an expression very familiar to the one mentioned above

To obtain Coulomb’s law from Maxwell’s equations you must set $\frac{\partial}{\partial t} \vec B =0$ and $\frac{\partial}{\partial t} \vec E =0$ and $\vec J =0$. So it is a special case which is only valid for static scenarios.
You can also derive Coulomb’s law from Gauss’ law and spherical symmetry, but a charge’s field is only spherically symmetric if it is at rest. So again, the static assumption is built in to Coulomb’s law.
