I used to use Mozy but when I tried a trial restore it was taking forever and missing some files. Also it inserts these .PART files into your system that can almost double the size of the folders you're trying to back up.
I looked at backblaze but it doesn't work with server computers.
So I'm now trying crashplan. I'm really interested in the feature of crashplan which allows automated backups to other computers. Only problem is that I've not been able to get this to work so far. Backing up to the cloud is working well though. Also its very competitively priced. I've yet to try a restore.
For servers, I've heard good things about Tarsnap, but never used it myself.
No, that's a tough one, especially with a back up the size you're doing.
Everytime you do a restore that's just confirmation that a particular backup was/was not sound.
Wouldn't it be neat if the back up program had functionality that allowed you to restore a random sample of your files ( and maybe then compare these to the originals ) and give you a likelihood that your entire backup is sound? A sort of sampling quality control process.
[1] though I'm switching off of them, not sure where to yet. There's some sort of issue in their client software that murders my home network, rendering the entire thing unusable while a backup is running. Their support was... less than helpful in trying to remedy the situation. For $5 a month and with the amount of stuff I was backing up, I can't blame them.
I don't have any QoS set up on my home network, I found two fixes: running the backup manually before going to sleep (maybe I can create an Apple Script and just cron this) or turning the Automatic Throttle off and giving it the minimum available (for me) 20kbps.