You have to realize that when we are speaking of photons, we are speaking of elementary particles and their interactions are dominated by quantum mechanics, not classical mechanics, and in addition special relativity is necessary to calculate anything about them.
In general, we know about elementary particles because we observe their traces in detectors for almost a hundred years. We never see an electron, or a proton in the way we see a particle of dust.
This is the most visual detector, a bubble chamber photo of electromagnetic events.
Here we see some electromagnetic events such as pair creation or materialization of high energy photon into an electron-positron pair (green tracks), the Compton effect (red tracks), the emission of electromagnetic radiation by accelerating charges (violet tracks) (bremsstrahlung) and the knock-on electrons or delta ray (blue tracks)
Now lets see about your questions:
1) How did we arrive at "electrons exchange virtual photons and that's the cause of the electromagnetic force between them" from merely observing electrons absorbing or emitting photons?
That is not the way we arrived at this conclusion. A very large number of controlled scatterings, which is what this picture shows, of electrons on matter have been studied over the years and the theoretical framework of calculating the probability of the scatter and the angular distributions has been very well developed for years. This involves mathematics which cannot be handwaved. To start with, the crossection of an electron scattering on an electron can be written in a series of convoluted integrals which can be pictorially represented by Feynman diagrams. In those Feynman diagrams, the propagators of the interaction between the incoming and outgoing particles can be thought as virtual photons because they carry the quantum numbers of the photon but are off mass shell. So it is a convenient mathematical identification which defines virtual photons.
Anything between the incoming vertices and the outgoing vertices is virtual, and their reality depends on the correct representation of the quantum numbers for the exchanged particle, in this case photon quantum numbers.
2) If electrons throw photons at each other doesn't that mean that they should only scatter (repel)? If that is so why do magnets attract?
Virtual photons are not like balls, they are off mass shell, they are useful a mathematical construct .There is an interesting analog though where two boats throwing balls at each other represent the repulsive forces, and boomerangs the attractive.
Do these two phenomena happen here on earth naturally (no LHC or other particle accelerators), in the upper atmosphere, or only in the deep dark space?
There exist cosmic rays of all energies, the cosmic accelerator, and elementary particles were first seen in emulsions exposed to cosmic rays in high altitudes, for example the pion was thus discovered. So any process seen in accelerators can be found if looking hard enough in cosmic rays. Accelerators allow detail and exact measurements of crossections and branching ratios etc. because of the high statistics possible.
I) At the perturbative/diagrammatic level of photon self-energy/vacuum-polarization $\Pi^{\mu\nu}$ , the photon masslessness is protected by the Ward identity, which in turn is a consequence of - you guessed it - gauge invariance. For the explanation in the setting of QED, see e.g. Ref. 1.
Fig. 1: A one-loop contribution to the photon self-energy/vacuum-polarization. More generally, the 'bubble' in the middle could be 'filled' with higher-loop contributions.
A brief oversimplified explanation is as follows: Mass is associated with a Feynman diagram in Fig. 1 and its higher-loop counterparts. The Feynman diagram is built from Lorentz-covariant tensor objects. The Ward identity states, loosely speaking, that the photon 4-vector $k^{\mu}$ is perpendicular to the Lorentz tensor structure of the middle bubble part of the diagram. In the end only the bare propagator/tree diagram without any loops/bubbles survives, thereby rendering the photon massless.
II) It should perhaps also be mentioned that in the Higgs mechanism, the fact that the Higgs field $\phi$ transforms in the fundamental representation of the electroweak gauge group $SU(2)\times U(1)~$ leaves one of the four gauge bosons without a massterm in the Lagrangian - the photon, cf. e.g. Ref. 2.
References:
M.E. Peskin & D.V. Schroeder, An Intro to QFT, Section 7.5.
M.E. Peskin & D.V. Schroeder, An Intro to QFT, Section 20.2.
Best Answer
Photons are quantum mechanical entities, so yes, it is a QFT case. Any interaction between two photons goes through exchange diagrams. Two photon interactions occur, with very low probability because the diagrams are box diagrams with at least four 1/137 couplings depressing the probability . For light frequencies this is a very small number . This probability grows with energy so even gamma gamma colliders are envisaged.