The second law of thermodynamics does not forbid the reversal of entropy per se, a point many people miss. It only forbids the reversal of entropy in the absence of a positive enthalpy gradient. As it happens, the earth has never had a shortage of positive enthalpy gradients, either a billion years ago or today. The sun provides most of that, and to a lesser extent nuclear decay and other enthalpy sources.
To put it another way, in addition to life, diamonds are also "impossible" unless positive enthalpy gradients reverse entropy, and there is no shortage of diamonds in the universe (de Beers notwithstanding). Quite frankly, the vast majority of non-living matter on this planet is also the result of some measure of entropy reversal by the same mechanism.