In this paper we use detailed Monte Carlo simulations to demonstrate that liquid xenon (LXe) can be used to build a Cherenkov-based TOF-PET, with an intrinsic coincidence resolving time (CRT) in the vicinity of 10 ps. This extraordinary performance is due to three facts: a) the abundant emission of Cherenkov photons by liquid xenon; b) the fact that LXe is transparent to Cherenkov light; and c) the fact that the fastest photons in LXe have wavelengths higher than 300 nm, therefore making it possible to separate the detection of scintillation and Cherenkov light. The CRT in a Cherenkov LXe TOF-PET detector is, therefore, dominated by the resolution (time jitter) introduced by the photosensors and the electronics. However, we show that for sufficiently fast photosensors (e.g, an overall 40 ps jitter, which can be achieved by current micro-channel plate photomultipliers) the overall CRT varies between 30 and 55 ps, depending of the detection efficiency. This is still one order of magnitude better than commercial CRT devices and improves by a factor 3 the best CRT obtained with small laboratory prototypes.