Tarsnap is really wonderful. I've been using it for about a month now and it's really simple. From your perspective, you're simply creating tar archives. No fuss, no muss.
On the tarsnap side, it makes sure not to duplicate storage or bandwidth for duplicate parts. Anytime you want to get a specific backup back, you just reference it by name. You can list the available archives. It's all encrypted. Pricing is based on what you actually use (rather than being rounded) which makes it ideal for small things as you can pay fractions of a cent.
On the tarsnap side, it makes sure not to duplicate storage or bandwidth for duplicate parts. Anytime you want to get a specific backup back, you just reference it by name. You can list the available archives. It's all encrypted. Pricing is based on what you actually use (rather than being rounded) which makes it ideal for small things as you can pay fractions of a cent.
It's definitely something to look into.