We are carrying out multi-frequency radio continuum observations, using the Australia Telescope Compact Array, to systematically search for collimated ionized jets towards high-mass young stellar objects (HMYSOs). Here we report observations at 1.4, 2.4, 4.8 and 8.6 GHz, made with angular resolutions of about 7, 4, 2, and 1 arcsec, respectively, towards six objects of a sample of 33 southern HMYSOs thought to be in very early stages of evolution. The objects in the sample were selected from radio and infrared catalogs by having positive radio spectral indices and being luminous (L_bol > 20,000 L_sun), but underluminous in radio emission compared to that expected from its bolometric luminosity. This criteria makes the radio sources good candidates for being ionized jets. As part of this systematic search, two ionized jets have been discovered: one previously published and the other reported here. The rest of the observed candidates correspond to three hypercompact hii regions and two ultracompact hii regions. The two jets discovered are associated with two of the most luminous (70,000 and 100,000 Lsun) HMYSOs known to harbor this type of objects, showing that the phenomena of collimated ionized winds appears in the formation process of stars at least up to masses of ~ 20 M_sun and provides strong evidence for a disk-mediated accretion scenario for the formation of high-mass stars. From the incidence of jets in our sample, we estimate that the jet phase in high-mass protostars lasts for 40,000 yr.