hedwards: I recommend Crashplan and a utility to check the integrity of the files. I realize you probably have a cap, but uploading a bit over the course of several months would provide a huge amount of protection against that.
drewpants: I may well give that a look - thanks.
The thing I like about them the most is that you can also have an onsite copy of your backups. If caps are a concern you can still backup all the stuff onto an external disk and then just spoon feed it a bit each month until you've got it all backed up.
I've got an uncapped connection and they're storing at least a terabyte of my data, so whatever you have is probably going to be limited only by any caps you might have and the ability to physically upload it.
Backblaze is another one worth considering, but I found the limited download time for restores to be problematic and I wound up losing files because of that.