The problem with VPSes at least is if anyone on the physical box manages to crash the machine, it goes out for everyone. Xen has historically been buggy -- just starting SBCL would crash it(!). Count on Murphy's law -- I had just finished some work and was waiting for a client to take a look at it, and of course my webhost decided to reboot the VPS right before the client checked. Since I hadn't put a restart in rc.local yet, it was just down.
Even with all your other ducks in a row, you don't want a third party rebooting your machine while someone is in the middle of using your site, especially if there's anything important going on, like customers purchasing with a CC or investors taking a look.
Jey's suggestion of cheap dedicated servers for $50 sounds better than EC2 if you're CPU-bound (2.5 GHz vs. 1.7) and is cheaper ($72 per node for 24-7 EC2 usage) and won't wipe everything on restart like EC2 does.
Note that mileage varies widely with webhosts. The majority of them do not understand even the basics of computer security, e.g. the importance of publishing their SSH key fingerprints (via https).