To some extent, use of e-mail encryption such as PGP/GnuPG or S/MIME would protect the content of individual messages stored on a service provider. However, as you note, ubiquitous encryption use doesn't exist today. There is a high barrier to entry in terms of key exchange, especially between parties with no previous introduction, and end-user experience (e.g., reading PGP encrypted e-mail on the Google Apps for your Domain Gmail web interface or on a mobile device such as the iPhone). Don't get me wrong, I hope we get there someday but the reality is we aren't there today.
However, even if that were in place, there is still information available to the service providers that can be quite useful to investigators. First, these encryption techniques will only encrypt the body of the message and attachments. Headers (such as sender, recipient(s), subject and date) are still exposed and, along with mail stream traffic analysis, can contain valuable information.
Additionally, by having the data in the cloud, even if encrypted, corporations lose the ability to control that data in terms of retention, backup, and auditing. For example, corporations could no longer guarantee a 90-day retention policy as they may not be able to mandate the same policy at a cloud provider, nor validate that it is actually being done properly (i.e., a message may disappear from view after 90 days but may not be deleted from the cloud provider's storage or backups). Likewise, there is usually no information audit as to where the message has been stored or which machines it has transited. You may not only be trusting your cloud provider, but the offsite backup service that provider uses or a chain of other providers (e.g., compute farms, storage services, etc).
The combination of traffic and header analysis and the ability to silently collect (potentially encrypted) messages over time beyond any corporate retention policy still leaves a corporation exposed to later subpoenas for the encryption keys to decrypt all content.
By the way, you state, "ALL email sent is by default in clear-text as it moves through MTAs, ISPs." That isn't completely accurate. The SMTP protocol includes support for STARTTLS encryption so the entire session is encrypted. Looking at statistics from our servers, close to 25% of the traffic from remote machines uses STARTTLS. In many cloud service offerings, STARTTLS is used to protect contents between the customer and service provider. However, this only protects the communication channel, not the data, which is typically stored in queues and stores unencrypted (or with an encryption key known to the service provider and therefore available to the investigators). Also, STARTTLS is hop-to-hop, not end-to-end.
Gregory Shapiro
VP, Engineering & CTO
Sendmail, Inc.
Topic: Cloud Computing
Software and data services are now viewed independently of distinct physical IT assets
Blog: Learning to Cope with Hard Disk Shortages
Article: A New Virtual Reality for Backup and Recovery
White Paper: Cloud-Ready Business Intelligence with Oracle Business Intelligence 11g
Related Topics
Anti-Virus Solutions, Data Loss Prevention
Mobile Collaboration SolutionsThis interactive demo shows four examples of how mobile collaboration solutions can drive business results for sales, marketing, executives and customer service.
Effective Storage Management for Cloud ComputingRead this white paper to learn how to reduce the complexity of managing cloud environments with a complete portfolio of automated solutions for managing data and storage infrastructure, enabling better efficiency for business resiliency, and helping to reduce costs and improve security.

Product information, vendor profiles, and expert commentary to help you decide whether to go with in-house customization, out-of-the-box convenience, or cloud-based hosting solutions for your data center improvements.
PGP or GnuPG make your concerns a non-issue.
Here's the silly part:
ALL email sent is by default in clear-text as it moves through MTAs, ISPs.
When you write a letter, do you not place it in a nice 'envelope'?: Yes.
Why?: Privacy.
That practice needs to be extended to email and nothing short of a Federal Mandate and global treaties for uniform PGP will get that to happen.
In the meantime, Corporate CIOs doing due diligence, risk analysis for when and how to best use the Cloud should avail themselves to all 'best of breed' technologies, including PGP or GnuPG for any sensitive email transmissions.
Dietrich T. Schmitz
Dietrich T. Schmitz & Associates
Cloud Computing Services