In my experience a lot of services make all kinds of promises in the features list on the front page but either cut you off at the knees with the details in the EULA, or end up going out of business.
One thing that's going to be important with any cloud service is trust, specifically the following:
- Sustainability of their business model is a good point... no use having a backup service that goes out of business.
- Data security (keep in mind that a service that looks ideal may be great but may do things with your data that aren't allowed, e.g. EU data privacy laws)
- Data integrity (a backup service that might delete some of your files is not a backup service at all).
- Service Level Agreement - if they're your backups, can you afford to have your business out of action because you lost a file, then when you went to do a restore the backup service has a problem and the one person who knows how to fix it is in Antigua for 2 weeks.
I think GregD's concerns over livedrive show that it might be very difficult to find a service that is flat rate AND meets the above criteria, plus anything else I missed out.