In plasmas at very low temperatures formation of neutral atoms is dominated by collisional three-body recombination, owing to the strong ~ T^(-9/2) scaling of the corresponding recombination rate with the electron temperature T. While this law is well established at high temperatures, the unphysical divergence as T -> 0 clearly suggest a breakdown in the low-temperature regime. Here, we present a combined molecular dynamics-Monte-Carlo study of electron-ion recombination over a wide range of temperatures and densities. Our results reproduce the known behavior of the recombination rate at high temperatures, but reveal significant deviations with decreasing temperature. We discuss the fate of the kinetic bottleneck and resolve the divergence-problem as the plasma enters the ultracold, strongly coupled domain.