I have found Linode disks to have the best performance in all
http://pastebin.ca/2049137
You are correct, I/O is the challenge in administering systems in a virtual environment. My database which does not fit in memory does fine on a high-load site because I cache it responsibly. For comparison, here are awful results from a new player called ChunkHost, who I signed up for with the purpose of testing
http://pastebin.ca/2049142
The sequential write throughput there is troubling. This comparison from a couple years back is interesting too
http://journal.uggedal.com/vps-performance-comparison/
I've linked this URL before but it really does the best of breaking it down. What cloud providers have you tried? In my experience there are vast gaps between certain ones, Amazon no exception. Hard to stereotype cloud with gaps like those.
Even if SoftLayer could provision me a new box in ten minutes the improvement to my sleep from not waking up for every disk failure and submitting a remote hands ticket at who knows how much per pop far outweighs anything else.