Do free electrons (plenty of them in space and in stars) scatter every photon they come across?
Free electrons, unlike those in atoms and molecules, don't have specific energy levels after all...
Isn't this what happened before the Era of Recombination and the release of the CMB? Every electron interacting with every photon, constantly?
I assume the electron would change its acceleration, velocity or direction depending on the strength of the photon... Correct?
In quantum mechanics, I think it is hard to define what 'contact' or 'come across' mean - the particles either interact with each other or they don't, with rules determining the probability. The phenomenon in which a photon and an electron interact and in which there is a momentum transfer is known as Compton scattering - a representative first order Feynman diagram of the interaction can be seen below (from wikipedia).
Note the photon above is scattered - the incoming (left) and outgoing (right) photons (same goes for the electrons) have different momenta. The complete absorption of a photon is kinematically forbidden (see e.g. this post).
The Compton scattering is a process that happens with some probability, when a photon "comes across" a free electron. This probability can be calculated from these Feynman diagrams.
(image from Pitfalls in the teaching of elementary particle)
But of course it is also possible that no scattering happens, like in this trivial Feynman diagram.
To "collide" with an electron at non-relativistic energy, the photon must "hit" it within the Thomson cross-section $\sigma_t$. This is very small, $\approx 6.65\times 10^{-29} m^2$. But the best you can focus light is given by the Airy disk, which (optimistically) has a minimum radius of the wavelength. So divide the cross section by the area you can focus light onto, $\pi \lambda^2$, to get the maximum probability of an interaction of an electron with a passing photon (valid for small probability). For green light, $\lambda\approx 500\ nm$, the probability is $\approx 10^{-16}$.
The Thomson cross-section represents the sense in which the photon is a "particle" that can "collide" with an electron, but mathematically it comes from a classical model of the interaction of electromagnetic waves (no photons involved) with charged particles. We use it because it gets the right answer, matching experiments. Don't take the "particle" idea too seriously: your intuition about particles (and waves) is not a terribly good guide to quanta. At gamma ray energies, the models are necessarily more complicated, and require that you treat the electron as a "wave" also.
