The maximum distance for which Coulomb's law has been verified? We know that Coulomb's law, $F_{12} = \frac{kq_1q_2}{r^2}$, was experimentally verified for small distances by Coulomb himself at the and of the XVIII century.
The question is what is the maximum distance, experimentally confirmed, between two charges for which Coulomb's law still holds?
 A: There have been lots of experimental attempts to test the validity of Coulomb's $r^{-2}$ law. Many of these are reviewed by Tu & Luo (2004), and is where I am getting the numbers quoted below. Somewhat equivalently, experiments have looked at trying to set an upper limit to the photon mass, which is testing the hypothesis that rather than a $r^{-1}$ relation, that the Coulomb potential falls in a similar way to the Yukawa potential, as $r^{-1} \exp(-m_\gamma c r/\hbar)$.
The laboratory tests largely involve measuring the potentials on concentric charged spheres and are relatively small scale. These show that if Coulomb's law  scaled as $1/r^{2+q}$, then the current limits are $|q|< 10^{-16}$. On the (laboratory) scales probed by the experiments, this corresponds to an upper limit to the photon mass of $m_\gamma < 10^{-50}$ kg (Crandall 1983; Fulcher 1986).
The size of laboratory equipment limits the constraints one can put on the mass of the photon and the scale-length of any Yukawa-like potential. However, on large scales, a non-zero photon rest mass would lead to a number of observational effects. Not only is the potential changed, but there is a predicted frequency-dependent velocity and the possibility of longitudinally polarised photons. The most stringent limit appears to come from considering the stability of magnetised gas in galaxies, where the claim is that the photon mass must be less than $10^{-62}$ kg, which is equivalent to a Yukawa-like scale length of 1000 pc! (Chibisov 1976). It is not clear how seriously this claim is taken, but Tu & Luo (2004) list several other cosmological and laboratory studies that have placed limits on any scalelength of $>10^{10}$ m.
At a distance of 1000 km, these deviations would amount to a difference in force of $\exp(-1000)$.
So from the point of view of your question, there is experimental evidence that the deviations from the Coulomb law are  utterly negligible at scales of 1000 km.
A: Coulombs law as well as Amperes law and similar mathematical formulations of two centuries ago, were incorporated  within the strict mathematical format of Maxwell's equations .

The apparently disparate laws and phenomena of electricity and magnetism were integrated by James Clerk Maxwell, who published an early form of the equations, which modify Ampère's circuital law by introducing a displacement current term. He showed that these equations imply that light propagates as electromagnetic waves. 

Coulomb's law can be derived from the first of Maxwell's equations in this list.
Solutions of Maxwell's equations are what we are using to communicate on the net with, let alone all the electricity usage , wireless etc. Our technology rests on Maxwell's equations being valid.
One does not need to do long range experiments with individual charges because the law will hold for all distances where Maxwell's equations are valid. This means non General Relativity range where it has to be adapted. A version of Maxwell's equations exists in the quantized theories too .
If the first law from which Coulomb's equation is derivable, were not valid over the whole distances (all of earth, and laser light to the moon)  where Maxwell's equations have been fundamental in constructing all our technology, there would have been discrepancies and Maxwell's equations would have been invalidated.
Here is a relatively recent (1970) test of Coulomb's law which gives an accuracy of $1.3 \times 10^{-13}$, compared to Coulomb's measurement (two hundred years before) of $4 \times 10^{-2}$. Concentric spheres are used and dimensions are of order of a meter. 

Note that the technique relies completely on Maxwell equations being exact, as it uses electromagnetic waves for the detection of an anomaly.
A: If you want to research the question more deeply, I would suggest you take a look at the Solar Wind. This is composed of charged particles (mostly protons) emitted by the Sun. The flow and behaviour of the Solar Wind has been studied quite deeply, not least because it affects greatly satellite operations, spaceflight, radio transmission and other important activities.
The Solar Wind is an example of charged particles interacting with solar and planetary magnetic fields at scales of mega-km. If there were any deviation from $1/r^2$ in Coloumb's Law that only became apparent at interplanetary distance-scales, we would expect to observe an anomaly in the behaviour of the Solar Wind.
I don't know of any such anomaly, but it might be a good place to look.
A: I might be erring something basic here, so downvotes are welcomed, but I would love if they include comments to correct this answer, or just erase it.
I do not believe the Coulomb law has been tested beyond the order of a few meters. Arguing that light remains unchanged across the universe should be irrelevant. The reason is that the electrostatic and electrodynamic parts of Maxwell's equations can be decoupled.
The way I see this is that you can argue that Maxwell's equations are a result of imposing Lorentz invariance on Coulomb law. The same was attempted with gravitation, and there are several ways to do it. Einstein's equation proved to be the most successful, both experimentally and aesthetically, but there are other potential generalizations that result in alternative gravitomagnetic effects (i.e., Nordstrom theory). 
The reverse is also true; you should be able to keep electromagnetic waves in vacuum unchanged by modifying Gauss law only. The reason being that electromagnetic propagation in vacuum only requires  $\nabla . E \neq 0$. Using $\nabla . E = 0$ still describes electromagnetic waves in the absence of a static force. A modification of the Gauss law (similar to those used in Lorentz invariant MOND's
theories) could be in principle made (I am not aware if  this has been shown impossible) that results in  a modified Coulomb force, is Lorentz invariant, and leaves the propagation of light in vacuum for infinite distances unchanged.   
