The space astrometry mission Gaia will construct a dense optical QSO-based celestial reference frame. For consistency between optical and radio positions, it will be important to align the Gaia frame and the International Celestial Reference Frame (ICRF) with the highest accuracy. Currently, it is found that only 10% of the ICRF sources are suitable to establish this link, either because they are not bright enough at optical wavelengths or because they have significant extended radio emission which precludes reaching the highest astrometric accuracy. In order to improve the situation, we have initiated a VLBI survey dedicated to finding additional suitable radio sources for aligning the two frames. The sample consists of about 450 sources, typically 20 times weaker than the current ICRF sources (down to the 20 mJy flux level), which have been selected by cross-correlating optical and radio catalogues. This paper presents the observing strategy to detect, image, and measure accurate positions for these sources. It will also provide results about the VLBI detectability of the sources, as derived from initial observations with the European VLBI Network in June and October 2007. Based on these observations, an excellent detection rate of 89% is found, which is very promising for the continuation of this project.Read less <