I know this is a sleeper of a thread, but I thought I'd pitch in here. It won't answer your question, but it will give you a necessary warning.
I shopped around quite a lot for online backup, and all I can say is, its time has not yet come.
My requirements were 1) 1+TB storage, 2) nothing gets deleted unless I approve, 3) cheap, and 4) encrypted.
I ended up going with ElephantDrive, because Mozy deletes any "missing" files since the last time you synced. There are a few other services out there that run as cheap as ED, but ED seemed pretty reliable, running on Amazon's A3 storage platform. To their credit, ED's support team is incredibly, incredibly helpful. They're working very hard to make it work for users.
The problem is that the upload rate is nil. I have about 250GB to back up, and after a full week of leaving my laptop running on a T1/T2 campus ethernet line, I was only at 3% done. This is not an exaggeration. They promise that the delta-sync after you finish the first backup goes much, much faster. But it's really not worth the front-loaded effort.
I cannot imagine that other online backup services are significantly faster in their upload rates. You should, however, test out the "free accounts" for upload speed, and try the top contenders out for a month.
It's not a matter solely of bandwidth. What you'll find is that all of these services have a file verification protocol that jams up the works. One service may have a faster one than another. But, to take an example: If you built an ISO file of of CD size (~700MB), you may have to wait 3-4 hours for that to upload. If any of the data packets don't get delivered, it has to start over, either in part or in full. It left me flabbergasted.
Be prepared for a messy breakup with whichever service you choose. And, if you have time to test the upload speed of ED versus other services, it would be great if you could post back here and let us know.
Cheers!