The circum-galactic medium (CGM) is believed to be made of warm-hot gas at a temperature close to the virial temperature of a galaxy. Indeed, X-ray observations have shown that the Milky Way CGM contains gas at about a million degrees. Recently using unprecedented high S/N XMM-Newton spectra in the sightline to 1ES1553+113 we discovered a very hot gaseous component of the Milky Way CGM, at ten million degrees. We also found non-solar abundance ratios and alpha-enhancement of light metals. Excited by this discovery, we explored other sightlines to determine how ubiquitous is this newly discovered hot component of the Milky Way CGM. Using Suzaku observations we have found similarly hot gas along three other sightlines, showing that the 1ES1553+113 sightline is not unique. These results provide insights on the heating and chemical enrichment of the Milky Way CGM, and provide important inputs to theoretical models of galaxy formation and evolution.