If your network is having almost 4 hours of downtime per month, it's time for a new network, to be honest.
Even if you reboot the server once a week (which is ridiculous), you're only talking about 20 minutes of downtime per month, and that's on the high end, with a crazy 5 minute reboot. That equates to a 99.95% uptime. Hell, our datacenters change entire raid arrays and swap out RAM in less time than that. Anything much beyond that and clients should absolutely be compensated for the downtime.
I honestly don't get how hosts are saying that hours and hours of downtime every month is somehow acceptable. There is obviously an acceptable amount of downtime, as no service (including cloud) can really guarantee 100% uptime. That amount of acceptable downtime, however, shouldn't be anywhere close to hours every month.