It can be done! But a lot depends on the hardware.
KVM and Xen are indeed the most obvious choices, along with Microsoft Hyper-V and VMware ESXi (both commercial).
I have written a how-to for installing a Xen hypervisor and then Windows as a guest OS with Windows having direct access to the graphics card. Here is my how-to: http://forums.linuxmint.com/viewtopic.php?f=42&t=112013
Using this how-to with some slight modifications, you should be able to get a multi-seat setup.
Here are some steps:
1. Check your hardware!!!!!!!!!!!!!!!!!!!!!!!!!!!
a. You need a VT-d compatible processor that supports IOMMU. See the how-to for how to figure that out.
b. The video card / GPU must support VGA passthrough. Most recent AMD cards do, so do the Intel CPU internal GPUs. Some few Nvidia cards are reported to work, most notably the Quadro series starting with the Quadro 2000 (not the 400 or 600) - see how-to.
Your ideal hardware would include the following:
- Intel CPU (non-K version) with internal GPU and VT-d support (or AMD CPU/board, as long as it supports IOMMU)
- Motherboard that has a IOMMU / VT-d config option
- 2 AMD graphics cards
- 2 or better 3 USB controllers (most boards have at least 2)
- 2 LCD screens, preferably with HDMI link and perhaps builtin speakers.
2. If, and only if you got the right hardware, follow the steps in the tutorial. Use LVM for storage - it's great and you don't want anything else. See the link to my other how-to on how to install Linux Mint on LVM.
3. Follow the tutorial and install the Xen hypervisor, etc.
4. Instead of installing one Windows guest system, you install two. To each Windows guest, you assign its own graphics card and USB controller. If you have 3 USB controllers in total, and 2 dedicated VGA cards as well as a CPU internal GPU, you can run 2 Windows desks and
a Linux desk simultaneously. When installing the Windows guests, do one by one - first release the PCIs for the first Windows guest and install it, and then install the graphics driver in Windows. When everything works, install the second Windows guest.
a. If necessary use VNC or ssh to connect from a remote computer (you can use virt-manager for that), as you may not have a screen output when you detach the graphics cards from Linux (using pciback, you'll see in the how-to).
The reason why Xen is the preferred solution over KVM is that KVM still may have some problems, for example when you shutdown the guest the host stops responding and needs a restart. Xen has also better documentation, and lots of features.
There are probably easier ways in getting a multi-seat solution, but I know of no other solution that provides even closely the performance of this Xen VGA passthrough solution.