We present 1.3- and/or 3-mm continuum images and 3-mm spectral scans, obtained using Northern Extended Millimeter Array (NOEMA) and Atacama Large Millimeter Array (ALMA), of 21 distant, dusty, star-forming galaxies. Our sample is a subset of the galaxies selected by Ivison et al. on the basis of their extremely red far-infrared (far-IR) colours and low Herschel flux densities; most are thus expected to be unlensed, extraordinarily luminous starbursts at z ≳ 4, modulo the considerable cross-section to gravitational lensing implied by their redshift. We observed 17 of these galaxies with NOEMA and four with ALMA, scanning through the 3-mm atmospheric window. We have obtained secure redshifts for seven galaxies via detection of multiple CO lines, one of them a lensed system at z = 6.027 (two others are also found to be lensed); a single emission line was detected in another four galaxies, one of which has been shown elsewhere to lie at z = 4.002. Where we find no spectroscopic redshifts, the galaxies are generally less luminous by 0.3-0.4 dex, which goes some way to explaining our failure to detect line emission. We show that this sample contains the most luminous known star-forming galaxies. Due to their extreme star-formation activity, these galaxies will consume their molecular gas in ≲ 100 Myr, despite their high molecular gas masses, and are therefore plausible progenitors of the massive, `red-and-dead' elliptical galaxies at z ≈ 3.