Why can't Compton scattering happen in leading order of perturbation theory? Why is the matrix element of Compton scattering in leading order of perturbation theory equal to zero? Why can this process only be described in second order of perturbation theory, i.e. with exchange of a virtual photon? Is there a physical reason?
 A: Absolutely.
If Compton scattering occurred in first order in $e$, the only contributing diagram would be the obvious one. Say we're in a frame with the electron initially at rest and an incoming photon in the $z$ direction. Then the electron 4-momentum is
$$p^\mu_{\text{in}} = (m,0,0,0)$$
while the photon 4-momentum is
$$k^\mu_{\text{in}} = (\omega,0,0,\omega)$$
Post scattering, there is only an electron moving upwards in the $z$ direction. Its momentum must be the same as the initial momentum, so if this process makes sense it should be
$$p^\mu_{\text{f}} = (\sqrt{m^2 + \omega^2},0,0,\omega)$$
However, $\sqrt{m^2 + \omega^2} \neq m + \omega$ so the process is forbidden by conservation of energy.
Another way to see that this amplitude must vanish is to realize that this diagram is related by "crossing" symmetry to a diagram that represents the decay of a single photon into an electron-positron pair. If this process were allowed at all we'd be in big trouble because we can always make the photon energy arbitrarily small/large by boosting. So we'd be able to freely move between a reference frame in which $\omega \geq 2m$, where the decay is "allowed", and one in which $\omega < 2m$, where it is forbidden. Lorentz invariance just died a painful death.
For the same reason, it's impossible for an electron positron pair to annihilate and produce a single photon. You must make at least two.
