I use Mozy and have had to restore from it TWICE (to new computers). Worked perfectly both times. My experience couldn't have been better.
I use Carbonite at work, and it works well backing up. I've never had to restore from it though. We used to use an external hard drive at work, and 1, we never remembered to use it, and 2, we never remembered to take it home, so if there had been a fire or something at the site the data would have been gone.