Never tried Carbonite, but I did try Mozy.
Mozy claims to encrypt the data as it is uploaded, and it's encrypted as it sits on their servers. Supposedly this means that even they can't access it, only I can with my password. I don't know about that since it could be public/private encryption and they could be holding one of the key pairs. I'm not an encryption guru and frankly try to stay away from the stuff whenever possible, but I figured "what the heck" for this bit of experimentation.
I sent up about 500MB of data, then brought it back down a couple months later.
Most of it came back down, but some of the documents that were restored, ended up corrupted on the restore. Excel and Word docs.
I did a second restore and the exact same files were corrupted again.
I checked the original data, and it was all fine. I could open the original files.
Take it for what it's worth as anecdotal tales, but I ended up not opting to trust it as a backup solution. I instead use an external HDD for routine data, and for "zOMGImgonnadieifIlosethis" files I have a copy on my PC and on a thumbdrive that I typically keep with me.