I've rambled a bit. Sorry.
Tezfair, I humbly apologise if you're aware of all of these things, but your post sort of suggests that you aren't.
Paravirtualisation shouldn't really be compared to hardware enabled virtualisation. There is a definite performance difference. Doubly so on modern hardware. Typically we find at work that it's actually the number of spinning disks, rather than CPU constraining an average virtual server host box - provided you put in a decent Xeon, or pair of Xeons.
If you're stuck with Windows, for your client, you may also want to look at Microsoft's RDS (Remote Desktop Services, previously Terminal Services). The licensing is a bit easier to swallow than VDI. All you need is Windows Server, the relevant RDS CALs, and you can re-utilize even the oldest hardware - provided you can run a RDP client - which there are for most platforms now. You could even consider using thin clients, if new client hardware is required. Generally speaking it normally works out cheaper than VDI for smaller numbers.
The problem is the nature that it's a shared box, and it may be a hurdle to get over for users, that they shouldn't be able to do what they want with their session. However, if you're from a *ix background you'll probably appreciate this and can deal with the situation and the users.
On the subject of the cost of the OS - again, Microsoft Windows have very specific amendments for virtualisation in the recent server and desktops licenses. For example Windows server 2008 standard allows you to run the same license on the host and in a single virtual machine. Enterprise upto 4 virtual machines, and datacentre is unlimited. There is also Windows Hyper-V server - a free, "GUI-less" (I use that term loosely) edition.
If you're not using Windows for the host box then the licensing applies as necessary.. Last time I played with it, Windows Server ran acceptably under Linux's KVM implementation for light-medium weight loads. VMware, yeah you're right on that front for the cost :)
If you're going for VDI then the licensing requirements are a bit more complex. I believe it's a requirement for volume licensing - although it's been a while since I've had to do a VDI install, so I may be a little out of date and off on that.
I'll get me coat.