Even if you don't get a formal service level agreement (SLA) from a service provider during the pre-sales process, you should get one before you commit to any type of service like this if you're a business. At a minimum, this type of agreement should include specifics around service availability, how often you have to bring the service down for maintenance or planned or unplanned downtime. Are they truly 24/7, every day of the year, or do they have conditions in which they are not available at all times?
While this may not be important to some businesses, it may be in the future as they grow. Also, are your support engineers, if needed, going to be available day and night? Restores aren't always happening at the most timely or convenient times, so service availability is another big one. Also, how the company handles incidents and provides escalation statistics. Who to contact, what level, when and what are the response times if you do have an issue?
All of these things are very unlikely to become issues, but they are a good thing to look for when you are dealing with a service provider. Also, when you look at guaranteeing backup and restore performance, it's fairly tricky territory in large part because all of these services depend on LAN or internet bandwidth. This can vary tremendously based on geography, latency, hops across network channels and other factors.
You will rarely see guaranteed speeds and performance for backup and restore. So, as a practical approach beyond the contract, you should definitely look for service providers to be able to measure, either during the pre-sales process or during initial deployments, what your actual backup and restore speeds are and to help you identify whether or not you have resource constraints on the WAN and if so, how do you mitigate those constraints.
Check out the entire Backup as a Service FAQ.