I strongly suspect this is a platform-specific complaint. As in, if you are running your Linux VMs on a z-Series from IBM this is manageable. It's just a question of what your customers are willing to pay for...
One of the nice things about Xen is that disk I/O can be controlled somewhat because each domU has a specific process in dom0 for disk access. So you can ionice things & provide a somewhat more controlled access to the disk.
My experience? it's easy to make one customers's I/O suck with such tools, but they work for shit when it comes to fairly balancing everyone's I/O.
As far as I can tell, the best practice is to monitor everyone's usage, and if someone goes above some pre-set threshold, to make their I/O suck using ionice or what have you.
But that's a long way from solving the problem.
Basically, CPU time is an abundant resource that's easily partitioned, but can be shared. So, you're guaranteed your share, but you often actually get more than your share.
Memory is strictly partitioned. You always get your share, no more, no less.
Disk is almost impossible to partition fairly (performance, not space). Furthermore, the more active disk users there are the worse the total performance is, so if you're unlucky enough to have a neighbor that uses a lot of disk IO than you effectively get double screwed.
What would be interesting is if someone came up with a VPS with dedicated disk resources, but as far as I know no one has done that.