  We study a disordered classical Heisenberg magnet with uniformly
antiferromagnetic interactions which are frustrated on account of their
long-range Coulomb form, {\em i.e.} $J(r)\sim -A\ln r$ in $d=2$ and $J(r)\sim
A/r$ in $d=3$. This arises naturally as the $T\rightarrow 0$ limit of the
emergent interactions between vacancy-induced degrees of freedom in a class of
diluted Coulomb spin liquids (including the classical Heisenberg
antiferromagnets on checkerboard, SCGO and pyrochlore lattices) and presents a
novel variant of a disordered long-range spin Hamiltonian. Using detailed
analytical and numerical studies we establish that this model exhibits a very
broad paramagnetic regime that extends to very large values of $A$ in both
$d=2$ and $d=3$. In $d=2$, using the lattice-Green function based finite-size
regularization of the Coulomb potential (which corresponds naturally to the
underlying low-temperature limit of the emergent interactions between
orphan-spins), we only find evidence that freezing into a glassy state occurs
in the limit of strong coupling, $A=\infty$, while no such transition seems to
exist at all in $d=3$. We also demonstrate the presence and importance of
screening for such a magnet. We analyse the spectrum of the Euclidean random
matrices describing a Gaussian version of this problem, and identify a
corresponding quantum mechanical scattering problem.
