Xen has the ability to cap CPU usage with either hard or soft caps. Most VPS companies seem to use soft caps. That way, if there are 4 instances on the box and each is doing lots of stuff, they'll each get 25%. But if 3 of the instances are mostly idle not using CPU, but one needs more CPU it will be able to use extra. It works out really nicely because it means that your usage can burst at certain times when it's unlikely that your co-habitants are similarly bursting.
So to put it bluntly they are very nice and helpful, but stupid. I wouldn't trust them with my data. But I can see how some customers might prefer them, as there is always a nice person on the other end of the line...
Regardless, doesn't most vps instances have limitations built into their VPS instances? It shouldn't matter to other VPS in that box how much CPU is being used by other VPS, as long as they are within their limitations?
That was my experience with slicehost and other VPS
There's no reason to be assigning VPSes to particular machines in 2009 -- distribute the damn things instead of selling shared hosting like in the bad old days (except this time with VM overhead!).