We report sensitive ATCA radio-continuum observations toward IRAS 15596-5301 and 16272-4837, two luminous objects (> 2x10^4 Lsun) thought to represent massive star-forming regions in early stages of evolution (due to previously undetected radio emission at the 1-sigma level of 2 mJy per beam). Also reported are 1.2-millimeter continuum and a series of molecular-line observations made with the SEST telescope. For IRAS 15596-5301, the observations reveal the presence of three distinct compact radio-continuum sources associated with a dense molecular core. We suggest that this core contains a cluster of B stars which are exciting compact HII regions that are in pressure equilibrium with the dense molecular surroundings. No radio continuum emission was detected from IRAS 16272-4837 (3-sigma limit of 0.2 mJy). However, a dense molecular core has been detected. The high luminosity and lack of radio emission from this massive core suggests that it hosts an embedded young massive protostar that is still undergoing an intense accretion phase. This scenario is supported by the observed characteristics of the line profiles and the presence of a bipolar outflow detected from observations of the SiO emission. We suggest that IRAS 16272-4837 is a bona fide massive star- forming region in a very early evolutionary stage, being the precursor of an ultra compact HII region.