BL Lacertae (Lac) objects that are detected at very-high energies (VHE) are of fundamental importance to study multiple astrophysical processes, including the physics of jets, the properties of the extragalactic background light and the strength of the intergalactic magnetic field. Unfortunately, since most blazars have featureless optical spectra that preclude a redshift determination, a substantial fraction of these VHE extragalactic sources cannot be used for cosmological studies. To assess whether molecular lines are a viable way to establish distances, we have undertaken a pilot program at the IRAM 30m telescope to search for CO lines in three BL Lac objects with known redshifts. We report a positive detection of M_H2 ~ 3x10^8 Msun toward 1ES 1959+650, but due to the poor quality of the baseline, this value is affected by a large systematic uncertainty. For the remaining two sources, W Comae and RGB J0710+591, we derive 3sigma upper limits at, respectively, M_H2 < 8.0x10^8 Msun and M_H2 < 1.6x10^9 Msun, assuming a line width of 150 km/s and a standard conversion factor alpha=4 M_sun/(K km/s pc^2). If these low molecular gas masses are typical for blazars, blind redshift searches in molecular lines are currently unfeasible. However, deep observations are still a promising way to obtain precise redshifts for sources whose approximate distances are known via indirect methods. Our observations further reveal a deficiency of molecular gas in BL Lac objects compared to quasars, suggesting that the host galaxies of these two types of active galactic nuclei (AGN) are not drawn from the same parent population. Future observations are needed to assess whether this discrepancy is statistically significant, but our pilot program shows how studies of the interstellar medium in AGN can provide key information to explore the connection between the active nuclei and the host galaxies.