We report on ESO Very Large Telescope optical spectroscopy of 42 BL Lacertae objects of unknown redshift. Nuclear emission lines were observed in 12 objects, while for another six we detected absorption features due to their host galaxy. The new high S/N spectra therefore allow us to measure the redshift of 18 sources. Five of the observed objects were reclassified either as stars or quasars, and one is of uncertain nature. For the remaining 18 the optical spectra appear without intrinsic features in spite of our ability to measure rather faint (EW nearly 0.1 Angstrom) spectral lines. For the latter sources a lower limit to the redshift was set exploiting the very fact that the absorption lines of the host galaxy are undetected on the observed spectra.