We are a photo/video storage service.
Sticking points I see are, 1. If you get it wrong you'll need some form of UX that keeps the users from getting to angry about it. 2. The cost of moving the data between hot/cold storage might make this prohibitive until a much larger scale. 3. User behaviors might not be predictable enough.
Because there may be an inflection point that offering monetary compensation for data loss, rather than actually trying to store the data, would make more financial sense. I.e., "All data > than 2 years gets silently expunged, and anyone trying to retrieve it at that point gets $10 per gig in compensation for 'our mistake'".
Please don't actually consider that though.
(And if you don't already, I would also consider making it so items that are in the trash for some period of time, say 30 days, get deleted automatically as well, possibly with a reminder email a few days before)
(And lastly, depending on user profiles and usage, incentives around reducing resolution/quality of photos and video, and automating that in the app as part of the sync process, might provide some opportunities to reduce costs of storage > the lost revenue of cheaper plans.)