I haven't seen that paper but in my experience with thousands of Xen servers, the CPU overhead is less than 5% (typically about 3% or so), not sure what parameters are discussed when talking about how badly VM behave (obv. there's I/O contention for several VMs on a server etc)
