You may be confusing the concept of hardware-assisted virtualization with full virtualization. Moreover, the famous Xen paper you've linked to never claimed that x86 didn't support full-virtualization because it did thanks to VMWare.
> VMware [10] and Connectix [8] both virtualize commodity PC hardware, allowing multiple operating systems to run on a single host. All of these examples implement a full virtualization of (at least a subset of) the underlying hardware, rather than paravirtualizing and presenting a modified interface to the guest OS.
And no, I haven't forgotten about binary translation. As you mention, it was only used to replace privileged instructions and not a full-blown CPU emulator. VMware VMs still ran native CPU instructions, and the overhead incurred by translation is a whole different matter unrelated to my original point.