It's not just VPSs. A project I cofounded used a dedicated server running Debian from dreamhost (chosen because it was cheap and came with unlimited bandwidth). In setting the server up we removed apache and installed nginx.
Doing so broke the boot process!
IIRC Dreamhost support managed to find a way to manually boot the box but couldn't help with actually fixing it and then we found a way to hack up their scripts so it would boot by itself again.