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 the host galaxy. The new high signal-to-noise ratio spectra therefore allow us to measure the redshift of 18 sources. Five of the observed objects were reclassified as either 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 (equivalent width ~0.1 Å) 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 in the observed spectra.