Abstract: The shallow, all-sky Planck surveys at sub-millimetre wavelengths have detected the brightest strongly gravitationally lensed dusty galaxies in the sky. The combination of their extreme gravitational flux-boosting and image-stretching offers the unique possibility of measuring in extraordinary detail the galaxy structure and kinematics in early evolutionary phases through high-resolution imaging and spectroscopic follow-up. This enables us to gain otherwise unaccessible direct information on physical processes in action. However, the extraction of candidate strongly lensed galaxies from Planck catalogues is hindered by the fact that they are generally detected with a poor signal-to-noise ratio, except for the few brightest galaxies. Their photometric properties are therefore strongly blurred, which makes them very difficult to single out. We have devised a method capable of increasing the number of identified Planck-detected strongly lensed galaxies by a factor of about three to four, although with an unavoidably limited efficiency. Our approach exploits the fact that the sub-millimetre colours of strongly lensed galaxies are definitely colder than those of nearby dusty galaxies, which constitute the overwhelming majority of extragalactic sources detected by Planck. The sub-millimetre colours of the 47 confirmed or very likely Planck-detected strongly lensed galaxies have been used to estimate the colour range spanned by objects of this type. Moreover, most nearby galaxies and radio sources can be confirmed by cross-matching with the IRAS and PCNT catalogues, respectively. We present samples of lensed candidates selected at 545, 857, and 353 GHz, comprising 177, 97, and 104 sources, respectively. The efficiency of our approach, tested by exploiting data from the SPT survey covering ?2500 deg2, is estimated to be in the range 30%?40%. We also discuss stricter selection criteria to increase the estimated efficiency to ?50%, at the cost of a somewhat lower completeness. Our analysis of SPT data has identified a dozen galaxies that can reliably be considered previously unrecognized Planck-detected strongly lensed galaxies. Extrapolating the number of Planck-detected confirmed or very likely strongly lensed galaxies found within the SPT and H-ATLAS survey areas, we expect ?150 to ?190 such sources over the full |b|> 20° sky.