In the presence of quantum gravity space-time fluctuations, Lorentz invariance and/or spin-statistic relation and quantum coherence of particles may be lost and the latter may lead to an ill-defined nature of the quantum mechanical CPT operator. I first discuss theoretical motivations and estimates for such a CPT Violation, and then proceed to describe current experimental searches, including the VIP experiment and its upgrades for searches of violation of the Pauli principle, as well as searches of quantum-gravity-decoherence-induced CPT violation in entangled states of mesons of interest to this laboratory. Specifically, in the latter case, there is an effect, termed the omega-effect, which affects the Einstein-Podolsky-Rosen correlations of entangled particle states, in a characteristic way to be detected in principle in entangled neutral Kaon or B systems.