I've been using Linode for over a year now, and, unlike some lesser-known VPS hosts I've used, I've never been required to shut down my VPS by Linode. The only restarts have been ones I've initiated.
How do they go for years on end without requiring restarts and with no downtime? Isn't downtime inevitable when upgrading some parts of the host system? Do they simply perform as few updates as possible?
This isn't meant to be a Linode-specific question; I am only using them as an example because I have experience with them.
Linode (and some other cloud vendors) use Xen full virtualization to provide services for you. These full virtualization stacks also allow the virtual machines to move from host-node to host-node live. One of the greatest side-effects of this is that they don't have to take down customer VMs in order to patch a node. Just move all the VMs on that node else where, apply updates, reboot, migrate new ones in. Done.
What they don't do for you is keep your VM OS patched. You have to do that yourself.
If they've engineered their system right (and they have), they can apply the same methods for things like network switch updates, storage system updates, and router reboots.
Linode (and others) are what's known as Infrastructure as a Service (IaaS) vendors. They allow you to focus on only keeping the OS and application code maintained.