There's a story about a site named FaceStat that was linked on the front page of Yahoo! one day, and had to spin up several Slicehost slices, complete with load balancing and all (or most) of the trimmings. Unfortunately, the admin's site is suspended by bluehost (or someone), and I don't remember the details. Here's a post by Slicehost that is related: http://www.slicehost.com/articles/2008/6/4/facestat-scales-f...
It is definitely possible to create a VPS-based system to replace your dedicated servers. In fact, that is the direction a lot of people are going, because it's relatively cheap to spin up a new VPS to scale horizontally, as opposed to purchasing a new server. Without knowing what your needs are in more detail, I couldn't say with any confidence whether Slicehost or Linode would work for you, or something else.
Do note that many traditional datacenters are starting to offer some sort of "cloud" solution, or at least some solution involving virtual machines that they have made sure involves the word "cloud", for the buzz factor. So, you could find a reliable colo facility, and work with them to migrate to a VPS-like solution.