I still think you have private and public clouds confused. A private cloud would be a single physical server on-premises, or uplinked to the clients office from a datacenter via MPLS circuit, that is managed by a single client like XenCenter (XenServer), vSphere (VMware) or System Center (HyperV). This allows one to spin up multiple VMs that would logically sit on their internal network and be perfect for low-latency, internal applications.
A public cloud offering is where you have a scaleable cluster of compute nodes connected to a massive backend storage system (like a NetApp- or HP-iSCSI SAN) and is managed by a management server running OpenStack, CloudStack, OpenNebula or whatnot. This then allows any user to simply login and create a VM with no guarantee of low-latency connectivity or functionality of use for internal applications, which is what you get with big-cloud providers. I certainly would not recommend using Linode, Rackspace, etc. for an internal server due to security concerns. A public cloud offering is what my original post was referring to and I apologize if I confused you. In your situation, depending on how many clients you have, I would heed warning as to whether or not you want to go the route of an Enterprise-level cloud service provider; but I do wish you the best of luck. It isn't cheap, and it isn't easy. :P