Interplanetary Coronal Mass Ejections (ICMEs) have proven to be very complex phenomena, not easy to unveil using a single set of observations. We combine Ulysses observations of medium energy particles, solar wind plasma parameters, magnetic field, and charge state distributions of heavy ions in order to identify and characterize CME ejecta in the heliosphere. We focused on a special class of ICMEs, so-called magnetic clouds (MC). The large number of MCs detected by Ulysses allowed us to perform a statistical analysis of the freezing-in temperature and energetic particle population within MCs. Based on a larger statistical set of events covering a full solar cycle and all heliolatitudes, we can confirm previous findings of a significant temperature increase within MCs. Furthermore, we found that this increase occurs at all latitudes and phases of the solar cycle. Intensities of medium-energy particles are generally depleted or not changed inside the MCs. This behavior is, again, found at all latitudes and solar cycle phases.