I don't know if this is a crazy idea or if it creates scalability issues, but could you craft an algorithm to cold store data for users who do not show a need for instant access, and/or warm up the data when you predict it will be needed? Kind of like a physical logistics company would need to do with distributed warehousing.
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.
So from a completely evil (well, capitalist) perspective, do you have data on how often people retrieve backups, and at what 'age' they do so?
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'".
(A less evil approach that might still lead to reduced costs would be detecting old, unaccessed data of sufficient size and flagging it for users, with a small refund or service discount if they purge it. Though that assumes you have 'power users' who are storing massive amounts, to where the savings in storage costs would be worth it)
(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.)
"We used advanced machine learning algorithms to predict which users will need to retrieve which pieces of data in the future, and silently delete everything else."
What about storing the older things in some slower backup service that's slow to access but cheap? If the user eventually accesses those some day you would kick of some background job to get them fresh again. Not super UX friendly of course, but could reduce costs. Or is this already the standard thing to do?
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.