Why does recombination occur at all?
The recombination of a free electron with a positive charge results in the emission of a photon. This is the time-reversed process of photoionization. Generally speaking, if nature allows for some process to occur, then it will also allow for its time-reversed process. One reason to see why is to consider a system in thermal equilibrium. Such a system will be in detailed balance. A consequence is that the cross-section for a process like photoionization ($\sigma_{bf}$) will be related to the cross-section for its inverse process of recombination ($\sigma_{fb}$), and we can use thermal equilibrium to relate their values. In this specific case of photoionization and recombination, this is expressed in the Milne relations. Since these cross sections are intrinsic properties of photons and electrons, we can then apply these values to conditions outside of thermal equilibrium.
Incidentally, finding the correct values of $\sigma_{bf}$ (and hence $\sigma_{fb}$ via the Milne relation) is perhaps the biggest obstacle to getting quantitatively accurate predictions for ionization and recombination. Naturally the situation is best understood for hydrogen, but the situation gets murkier for many atomic levels for many heavier elements.
Dependence on density and temperature
Consider a number density of electrons $n_e$, traveling at velocity $v$, a number density of positive charges $n_i$, and the recombination cross section $\sigma_{fb,nl}(v)$ to a bound atomic level with quantum numbers $n$ and $l$ . Then the rate of recombinations per unit volume is
$$ {\cal R_{v,nl}} = n_e n_i \sigma_{fb,nl}(v) v$$
However, in a typical plasma the electrons will have a thermal distribution of velocities, specified by the Maxwell-Boltzmann distribution, $f(v;\,T)$. Here my notation is meant to suggest that at a given temperature $T$, $f$ will provide you with a distribution for the velocities. To account for this range of speeds, we must perform an integral over all possible speeds, weighted by $f(v; \, T)$ to find the actual recombination rate in the plasma to this atomic level.
$$ {\cal R_{nl}} = n_e n_i \int \sigma_{fb,nl}(v) \, v \, f(v; \,T) \,dv$$
This integral (not including the factors of $n_e$ and $n_i$ out front) has units of volume per time and is known as the recombination coefficient. You can see that it is temperature dependent, and it is often denoted as $\alpha_{nl}(T)$. Explicitly,
$$ {\cal R_{nl}} = n_e n_i \alpha_{nl}(T)$$
Higher temperatures cause $f(v, T)$ to give more weight to electrons moving at faster velocity. This leads to two competing effects. First, higher velocities mean the electrons will encounter more positive charges per unit time -- this is accounted for by the factor of $v$ in the first equations. On the other hand, the recombination cross section $\sigma(v)$ decreases at higher velocities, as you correctly hypothesized in your question -- faster moving electrons have an easier time flying right by a positive charge without being captured.
The second effect tends to dominate, and for a wide range of temperatures $\alpha$ tends to scale roughly as $T^{-1/2}$.
The number of positive charges in the plasma will usually be proportional to the number of negative charges, since most material is net neutral. So we can summarize by saying that the recombination rate scales roughly as density squared and temperature to -1/2 power.
Plugging in some numbers
For a hydrogen plasma at $5000$ Kelvin, $\alpha$ for recombination to the ground state is about $2.3 \times 10^{-13}$ cm$^{-3}$ ${\rm s}^{-1}$. If the temperature is raised by a factor of 4 to $20,000$ K, $\alpha$ drops to about $1.1 \times 10^{-13} {\rm cm}^{-3}$ s$^{-1}$
The typical time for an electron to recombine to level of interest is then $1/[ n_e \alpha_{nl}(T)]$. So for an electron density of $10^{23}$ particles per cubic centimeter, at $5000$ K electrons recombine to the ground state in a time of about $10^{-10}$ seconds. But that doesn't mean that the gas will necessarily become totally neutral in that time, because thermal processes (photons or electron collisions) will also be providing a competing ionization rate. There might also be an external source of ionizing photons that maintain the plasma's ionization state in photoionization equilibrium, as in a nebula.
There are more complications to consider. We've been considering recombination to one specific atomic level. For a complete calculation, you'd need to find $\alpha(T)$ for each level, and sum their contributions. Moreover, for recombinations to the ground state, the photon that is released can go on to ionize other atoms. For a sufficiently dense plasma, a useful short cut in this case is to sum the contributions of recombination to all levels except for the ground state and use this as the effective recombination coefficient. This is known as "case B" recombination, or the "on-the-spot" approximation, since it assumes that all ionizing photons released during recombination are re-absorbed right away, effectively cancelling out their contribution.
