I'd go for a hybrid approach: new data is stored on private cloud, and old data would be gradually migrated or phased out.