We've seen RFPs asking for 2 terabytes of data in the cloud with 24 hour recovery time, with the data encrypted at rest. I can't find anyone who can provide SQL Server Enterprise Edition (to use TDE and partitioning) at that scale as a cloud provider (which to me means the replication over to a failover node and data is handled by them, or so I hope). Just investigating this -- any suggestions?

Your point about data quality is very important. Having quality data, or at least understanding the limits of your data, is critical in any data mining exercise. Hopelessly wrong or no conclusions can be arrived at when the inputs are incomplete or put together incorrectly. I hope that companies recognize that data governance is worth putting more resources into.