Quasi-periodic oscillations (QPOs) are observed in the optical flux of some polars with typical periods of 1 to 3 s but none have been observed yet in X-rays where a significant part of the accreting energy is released. QPOs are expected and predicted from shock oscillations. Most of the polars have been observed by the XMM-Newton satellite. We made use of the homogeneous set of observations of the polars by XMM-Newton to search for the presence of QPOs in the (0.5-10 keV) energy range and to set significant upper limits for the brightest X-ray polars. We extracted high time-resolution X-ray light curves by taking advantage of the 0.07 sec resolution of the EPIC-PN camera. Among the 65 polars observed with XMM-Newton from 1998 to 2012, a sample of 24 sources was selected on the basis of their counting rate in the PN instrument to secure significant limits. We searched for QPOs using Fast Fourier Transform (FFT) methods and defined limits of detection using statistical tools. Among the sample surveyed, none shows QPOs at a significant level. Upper limits to the fractional flux in QPOs range from 7% to 71%. These negative results are compared to the detailed theoretical predictions of numerical simulations based on a 2D hydrodynamical code presented in Paper II. Cooling instabilities in the accretion column are expected to produce shock quasi-oscillations with a maximum amplitude reaching ~ 40% in the bremsstrahlung (0.5-10 keV) X-ray emission and ~ 20% in the optical cyclotron emission. The absence of X-ray QPOs imposes an upper limit of ~ (5-10) g.cm-2.s-1 on the specific accretion rate but this condition is found inconsistent with the value required to account for the amplitudes and frequencies of the observed optical QPOs. This contradiction outlines probable shortcomings with the shock instability model.