All but three (M87, BL Lac, and 3C 279) extragalactic sources detected so far at very high energy γ-rays belong to the class of high-frequency- peaked BL Lac objects. This suggested to us a systematic scan of candidate sources with the MAGIC telescope, based on the Donato et al. compilation of X-ray blazars. The observations took place from 2004 December to 2006 March and cover northern sky sources visible under small zenith distances zd < 30° at culmination, constraining the declination to -2° to +58°. The sensitivity of the search was planned for detecting X-ray-bright [F(1 keV) > 2 μJy] sources emitting at least the same energy flux at 200 GeV as at 1 keV. To avoid strong γ-ray attenuation close to the energy threshold, source redshift was constrained to z < 0.3. Of the 14 sources observed, 1ES 1218+304 (for the first time at VHE) and 1ES 2344+514 (strong detection in a low flux state) were detected in addition to the known bright TeV blazars Mrk 421 and Mrk 501, A marginal excess of 3.5 σ from the position of 1ES 1011+496 was observed and then confirmed as a VHE γ-ray source by a second MAGIC observation triggered by a high optical state. For the remaining sources, we present 99% c.l. upper limits on the integral flux ≳200 GeV. We characterize the HBL sample (including all HBLs detected at VHE so far) by looking for correlations between their multifrequency spectral indices determined from simultaneous optical, archival X-ray, and radio luminosities, finding that VHE-emitting HBLs do not seem to constitute a unique subclass. The HBLs' absorption-corrected γ-ray luminosities at 200 GeV are generally not higher than their X-ray luminosities at 1 keV. © 2008. The American Astronomical Society. All rights reserved.