The storage behind the Cloud matters. While many Cloud Services have service-level agreements (SLAs), the only thing that SLA is good for if your provider is down and can't return you to operations quickly is a lawsuit. Ask what these providers have in the back end for both their storage and recovery processes. Make sure they are using products that have a track record of being cost effective, redundant and reliable. You might be surprised at the answers.
For example, I was having lunch with the storage administrator of a local insurance company and we were talking about Cloud Services. His view was recently soured. One of the Cloud Services they were using had an outage, broke their SLA and the insurance company was without an important, not critical, service for almost two days. It turns out the provider of the service was running the application on internally installed RAID-5 and they had a double drive failure. Up until that point the storage administrator had never asked what was the storage behind the cloud. The only form of recovery for the provider was from tape, it took two days to order in new drives, install them in the area and recovery the application.