Mind if I jump in?...
Don't know about Carbonite, but Mozy would be expensive for that amount of storage, at least on their Pro plan, at $.50/gb. However, I must say I just cancelled a Pro plan after about 6 weeks of trying it on my server and three workstations. Very slow, very limited storage space for the money, and the desktop applications kept timing out and were not in sync with the online "dashboard".
I went back to on-site backups with Super Duper! (on a Mac) doing a modified clone of my drives each night. I say "modified" because it can do an incremental clone, only copying files that changed or were added.
I switched from a backup program like Retrospect to get away from the "big humongous file" methods these program use. I wanted something I could hookup and begin to work from ASAP in case of a primary hard drive failure, and not wait for a restore.
Hard drives are cheap at the moment, so I stocked up. I currently run 3 tb of "work-in-progress" disk space, and 4 tb of backup drive space, and still feel unprotected, so everything goes on duplicate DVDs as projects are completed or at specific calendar points; one set of DVD goes in the safe deposit box at the bank. My business depends on my data; data loss means the loss of business.
Can you tell I've had some catastrophic drive failures in the past?
I would recommend staying away from online backup, and just buying some local drives. Invest in some cloning software, and set it up to run each night. You'll sleep better for it!
Plus, it looks cool having all those drives lined up. And that's what counts, right???
My $.02.
gary