The Carbonite service sounds quite good. Also the price is reasonable.
The service I am also interested in is Amazon S3. Unlimited storage, you pay only for the space and tranfer you use, the price is low. Amazon is big and stable company - yes, it can disappear from the business but itīs not very likely.
Another big and stable company (HP) started to offer unlimited storage services - HP Upline .

Another thing I thought could be worth the money is buying some disaster proof storage. I donīt know much about it - this is just one of the examples that came out of the search engine: http://www.iosafe.com/ . Maybe it could be hidden well enough in order for possible thievs not to find it.

The important thing is to test the recovery procedure from your backup systems/archives to see if it works at all. Some backup files/archives can be corrupted, some backup software might backup with errors etc. I have read about one company that had purchased complete backup solution (I believe it was backup to tapes), they had turned it on and had not care anymore. When their primary storage hardware failed they wanted to recover the data from the backups. Only to find out that the software had been running in some sort of preview/test mode all the time and had not backed up any real data.