Storing it is fairly cheap:
- Voice can be approximated to 64kbps (mono, OK quality). If the four million devices spends one hour on the phone on average, that works out to 107TB a day. Expensive, but certainly feasible.
- Text messages are 160B a pop. Include metadata such as timestamp, recipient and sender, call it 300B. At 100 text messages per customer, that's 11GB a day. This is trivial. You could even store a years worth on a home budget.
- Browsing -lets say 500B per request. A webpage is easily 50 requests, and let's assume a customer does 500 web pages per day. That's 93GB, or 33TB a year.
All of these is of course Fermi estimates, and give a rather generous quota for use. Turns out, storing voice in good quality is the only thing that's expensive. The rest is dirt cheap to store. If you reduce voice to 10kb/s, which is enough for mono voice in low quality, you shrink that to 16TB a day.
So in terms of cost, it's feasible. It would probably impact the profits of the ISP quite significantly.