Where's their agreement with Microsoft?
Hosting Windows client OS (XP, Vista, 7 etc) and renting it out is a strict no-no. Microsoft do not allow it under SPLA (which is how everyone offering hosted services based on Windows has to license). The only workaround is to give each end- user their own hardware (i.e. no virtualisation, unless the server is hosting desktops for one company ONLY, which kills abilty for hoster to consolidate) and then you'd have to charge up front for retail licenses (what Desktone are doing IIRC).
You could put together a VDI service based on Windows Server (RDS) which you can make look and feel pretty much the same as a client Windows, and consolidate more (RDS supports multiple desktops per server) or give each user their own instance (if you want to give each user local admin rights). However, some applications will refuse to install on a server OS.
Lots of hosting companies have tried and failed to get Microsoft to budge on this, even when large amounts of money was waved at Microsoft. I can't believe OnLive are doing this without agreement with Microsoft, so maybe Microsoft has finally decided to allow hosters to offer VDI...