Context.The Red MSX Source (RMS) survey is a multi-wavelength programme of follow-up observations designed to distinguish between genuine massive young stellar objects (MYSOs) and other embedded or dusty objects, such as ultra compact (UC) HII regions, evolved stars and planetary nebulae (PNe). We have identified nearly 2000 MYSOs candidates by comparing the colours of MSX and 2MASS point sources to those of known MYSOs. Aims.There are several other types of embedded or dust enshrouded objects that have similar colours as MYSOs and contaminate our sample. Two sources of contamination are from UCHII regions and PNe, both of which can be identified from the radio emission emitted by their ionised nebulae. Methods.In order to identify UCHII regions and PNe that contaminate our sample we have conducted high resolution radio continuum observations at 3.6 and 6 cm of all southern MYSOs candidates ( $235\degr< l < 350\degr$) using the Australia Telescope Compact Array (ATCA). These observations have a spatial resolution of ~1-2´´ and typical image rms noise values of ~0.3 mJy - sensitive enough to detect a HII region powered by B0.5 star at the far side of the Galaxy. Results.Of the 826 RMS sources observed we found 199 to be associated with radio emission, ~25% of the sample. The Galactic distribution, morphologies and spectral indices of the radio sources associated with the RMS sources are consistent with these sources being UCHII regions. Importantly, the 627 RMS sources for which no radio emission was detected are still potential MYSOs. In addition to the 802 RMS fields observed we present observations of a further 190 fields. These observations were made towards MSX sources that passed cuts in earlier versions of the survey, but were later excluded.