There are lot of providers offering cheap dedicated servers which is better than any VPS solution, in my view bandwidth may not be a big issue but it depends on the clients who are going to use this backup solution.

Check the companies offering 10Mbps unlimited bandwidth many are there.