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.