The number one thing you want to be looking for is ease of use, ease of deployment and speed of deployment. After all, when you look back at the root cause of why companies are looking at these solutions, a lot of it has to do with the management complexities of existing solutions. You want to look for technologies that are part of the solution that minimize the impact of the network. Essentially after your initial full backup, are the technologies doing things like data deduplication or delta differencing or other block-based change mechanisms, so you're not doing large volume copies of your backups over and over. These technologies are out there, but the key thing to look for is whether the incremental or deduplicated backups going over the networks after the initial pull are being deduplicated at your end of the deal or at the service provider's end of the deal. There is a major difference that really equates to bandwidth consumption on the WAN as a result.
Another thing to look at is security. The bigger the organization, the more you are going to be concerned with things like access control lists, role-based authentication and role-based access to systems. For instance, let's say you're a company of 20 people and everyone is using this service, maybe you don't want everyone to have the equivalent of root level access to do resource. Be sure that if you need encryption, that part of the service offering is available. Also if you're doing encryption of data at rest on your side, understand how that impacts the effective amount of storage on the service provider end, and how that affects your contract.
Be sure that you have some visibility into what's actually happening, how much capacity you are using, what the performance looks like on a daily or weekly basis. How much storage is used, how storage is used, how much is backed up, what is used and when and what are the backup window times for the service.
Look for proof of infrastructure. Are the datacenters running the server owned or are they co-owned datacenters? Does the service provider have multiple datacenters, as in, if they have a disaster is your data gone indefinitely or has it been replicated to another site for disaster recovery? These are things that you would normally not think about since your data is moving offsite, yet if you're doing this for the long haul and putting your critical data assets in the hands of a service provider then it does matter.
Look for evidence of a company in technology stability. When you call, up does the CEO answer the phone or do you get a true support person? Also, where is that support person located? Then also look to see if they have 24/7 support. Even if you don't need or don't want to pay for it, whether or not that exists in a company is a huge indicator of company maturity. And lastly, if you need application awareness in the backup and restore process, such as application awareness of Exchange data stores or SQL, things that are very common in SMBs or remote sites, make sure that that application awareness is fully understood by the storage provider, so you have potential for restore consistency.
Check out the entire Backup as a Service FAQ.