What about Hetzner? I'm not sure how they integrate with other VPS providers but their storage is very very cheap and bandwidth is good enough.

I use a storage box for remote backups and have never had an issue. They do take the storage box servers offline for maybe 3 hours per year all together for maintenance, which can be annoying but at least it's announced ahead of time. In nearly two years there has been one unplanned outage which was solved in minutes.