We have made an extensive 1.2mm continuum mosaicing study of the Cygnus X molecular cloud complex using the MAMBO cameras at the IRAM 30 m telescope. We then compared our mm maps with mid-IR images, and have made SiO(2-1) follow-up observations of the best candidate progenitors of high-mass stars. Our complete study of Cygnus X provides, for the first time, an unbiased census of massive young stellar objects. We discover 129 massive dense cores, among which 42 are probable precursors of high-mass stars. Our study qualifies 17 cores as good candidates for hosting massive IR-quiet protostars, while up to 25 cores potentially host high-luminosity IR protostars. We fail to discover the high-mass analogs of pre-stellar dense cores in CygnusX, but find several massive starless clumps that might be gravitationally bound. Since our sample is derived from a single molecular complex and covers every embedded phase of high-mass star formation, it gives the first statistical estimates of their lifetime. In contrast to what is found for low-mass class 0 and class I phases, the IR-quiet protostellar phase of high-mass stars may last as long as their better-known high-luminosity IR phase. The statistical lifetimes of high-mass protostars and pre-stellar cores (~ 3 x 10^4 yr and < 10^3 yr) in Cygnus X are one and two order(s) of magnitude smaller, respectively, than what is found in nearby, low-mass star-forming regions. We therefore propose that high-mass pre-stellar and protostellar cores are in a highly dynamic state, as expected in a molecular cloud where turbulent processes dominate.