(abridged) Our project endeavors to obtain a robust view of multiplicity among embedded Class I and Flat Spectrum protostars in a wide array of nearby molecular clouds to disentangle ``universal from cloud-dependent processes. We have used near-infrared adaptive optics observations at the VLT through the H, Ks and L filters to search for tight companions to 45 Class I and Flat Spectrum protostars located in 4 different molecular clouds (Taurus-Auriga, Ophiuchus, Serpens and L1641 in Orion). We complemented these observations with published high-resolution surveys of 13 additional objects in Taurus and Ophiuchus. We found multiplicity rates of 32+/-6% and 47+/-8% over the 45-1400 AU and 14-1400 AU separation ranges, respectively. These rates are in excellent agreement with those previously found among T Tauri stars in Taurus and Ophiuchus, and represent an excess of a factor ~1.7 over the multiplicity rate of solar-type field stars. We found no non-hierarchical triple systems, nor any quadruple or higher-order systems. No significant cloud-to-cloud difference has been found, except for the fact that all companions to low-mass Orion protostars are found within 100 AU of their primaries whereas companions found in other clouds span the whole range probed here. Based on this survey, we conclude that core fragmentation always yields a high initial multiplicity rate, even in giant molecular clouds such as the Orion cloud or in clustered stellar populations as in Serpens, in contrast with predictions of numerical simulations. The lower multiplicity rate observed in clustered Class II and Class III populations can be accounted for by a universal set of properties for young systems and subsequent ejections through close encounters with unrelated cluster members.