First, you have to know what kind of cloud services you are talking about. When people talk about "eDiscovery in the cloud" they often mean delivering eDiscovery software as a service (SaaS). I wish they wouldn't call it a cloud because to my mind it's not, but this is the way of the world. SaaS is a time-honored way of delivering eDiscovery services and is a fine thing. Some eDiscovery applications are delivered to the enterprise and are run on-site, others are run on remotely hosted data. Either model works just fine. So if people are referring to this model when talking about eDiscovery in the cloud, then fine. I don't think they'll stop just because I find the cloud appellation irritating.
Now, if you're talking about eDiscovery in the cloud in terms of storage then you have got a far, far different challenge. As I recently shared with a journalist, companies have to be extremely careful when archiving to a cloud structure. And we need yet more definitions.
Some vendors like CaseCentral refer to their hosted site as a private cloud. This is not a bad thing and the "private cloud" term is becoming pretty common. EMC uses it and so do others. The essential idea is that a private cloud stores traditional enterprise data types and retains some level of traditional data protection. There is also a single owner, either the enterprise itself using a utility model of computing, or a vendor that provides customers with strongly segmented private storage.
The problem comes in with private or public clouds that cannot enable custody and control. That means public clouds like Amazon or Google. Public clouds are dangerously inadequate for long-term enterprise storage. They are really meant to support rich web applications for speedy delivery, most often by storing Internet objects accessed via HTTP or APIs. Traditional data protection features don't exist on this level of cloud, which automatically leaves out most business archiving on any serious scale. There is simply no way to track physical location, modification or security features on an individual file level, which is exactly what eDiscovery must allow you to do.