Our company has a Xen-based instance on a VPS provider and we have some sensitive data stored on it. Is there a way for me to tell if/when employees of the hosting company have accessed my VPS (by xen consoling into it, for instance?)
Xen allows for transparent copying of a live machine (with Remus). The guest system ("domU" in Xen terminology) needs not be aware of this process. Consequently, if the VPS provider employees are intent on having a look at your machine without being detected, well, they technically can: they "just" have to make a live copy. This is inherent to the concept of virtual machines.