It is more costly, but this is a good reason to use a dedicated chunk of memory for every Xen PV domU. No oversubscription!
Allowing multiple domU VMs on the same dom0 (or the equivalent in other hypervisor platforms) to re-use memory and balloon/contract memory on the fly is what enables this.