Comment 5 for bug 517060

linux-image-server (64-bit) or linux-image-generic-pae (32-bit) in lucid work just fine paravirtualised in Xen domU.

Admittedly the existence of a -virtual kernel is somewhat misleading in this case, but the paravirtualised kernels do exist.