This study presents first results from an X-ray mini-survey carried out with XMM-Newton to investigate the diffuse Hot Ionized Medium in the halos of nine nearby star-forming edge-on spiral galaxies. Diffuse gaseous X-ray halos are detected in eight of our targets, covering a wide range of star formation rates from quiescent to starburst cases. For four edge-on spiral galaxies, namely NGC 3044, NGC 3221, NGC 4634, and NGC 5775, we present the first published high resolution/sensitivity detections of extended soft X-ray halos. EPIC X-ray contour maps overlaid onto Ha imaging data reveals that in all cases the presence of X-ray halos is correlated with extraplanar Diffuse Ionized Gas. Moreover, these halos are also associated with non-thermal cosmic ray halos, as evidenced by radio continuum observations. Supplemental UV-data obtained with the OM-telescope at 210 nm show Diffuse Ionized Gas to be well associated with UV emission originating in the underlying disk. Beside NGC 891, NGC 4634 is the second non-starburst galaxy with a diffuse soft X-ray halo ("z" , 4 kpc). In case of NGC 3877, for which we also present the first high resolution X-ray imaging data, no halo emission is detectable. EPIC pn spectra (0.3-12 keV) of the diffuse X-ray emission are extracted at different offset positions from the disk, giving evidence to a significant decrease of gas temperatures, electron densities, and gas masses with increasing distance to the plane. A comparison between dynamical and radiative cooling time scales implies that the outflow in all targets is likely to be sustained. We find very strong indications that spatially correlated multi-phase gaseous halos are created by star forming activity in the disk plane. In a forthcoming paper, we will present multi-frequency luminosity relations and evaluate key parameters which might trigger the formation of multi-phase galaxy halos.