Is KVM paravirtualizaton a new feature?
It's possible to isolate the second part -- paravirtualized drivers -- without requiring the first part -- paravirtualized bootup. Since bootup isn't guest-assisted any more, the hypervisor now has to emulate the entire PC-compatible boot process, including minimal emulation of BIOS interrupts for disk access, etc. But once that's completed, you can switch to paravirtualized drivers for optimized performance, and the actual performance benchmarks people care about are the steady-state disk and network bandwidth.
The only somewhat tricky thing is that you need to handle MMU updates somehow. I believe (but don't know for certain) that with nested page table support at the processor level, you can just safely give x86 hardware-virtualized guests access to their nested page tables, and they can use the same instructions to modify that as they would on native hardware. So you don't need paravirtualization for that. This support has been in hardware since around 2008.
One of the benefits of using paravirtualized drivers alone, instead of an entire paravirtualized boot process, is that you can support OSes where you can write custom drivers but you can't change the boot code. So, for instance, the KVM project has Windows disk and network drivers that use the paravirtualized interface (virtio):
You can continue to use Windows without this support, which will use the slow, emulated disk and network hardware. But if you have the drivers, things will get much faster. This is a best-of-both-worlds approach: you can continue to run any OS (since full virtualization support remains present), but you can switch to the paravirt drivers and get steady-state performance competitive with paravirt-only hypervisors.
Paravirtualized KVM uses virtio devices rather then emulated devices. So, instead of a virtual e1000 device, you'll see a virtio-net device. Performance gains are very, very significant.
Paravirtualization is just an extension of what you think is "full virtualization"
BTW, In case this article was misleading: I think Xen already has paravirt support that VPS providers already take advantage of.
Paravirtual IO drivers, you have a front end driver in the guest, and a back end driver elsewhere. In Xen, this is a dom0 or stub domain that also includes the actual hardware driver. With Xen the front end and back end are just a shared memory segment using a ring buffer. KVM does things a bit differently, but the core concept is pretty similar.
SR-IOV you have a virtual function of the device that is passed through directly to the guest, eliminating the need for the PV IO drivers at all.