The fact that large, centralized storage becomes expensive quickly will, I think, be a limiting factor in the growth of the relay network. An obvious solution is for relays to shed events based on some heuristic to prevent storage from growing out of control. This keeps relays affordable, but makes user data ephemeral.

To store events long-term, the user has to either ensure they are distributed across many relays so they are always out there somewhere, or pay for the storage space themselves.

I think paid storage is more likely. Some relays already do that; Wine is an example.

Another solution would be tiered storage. Perhaps some solutions will implement user-controlled cloud storage as a second tier. The user can designate outbox relays and event kinds to be stored long-term, and the second-tier permanent storage vacuums up the user's events from their outbox relays and stashes them. That storage solution can provide a DVM that re-introduces events to the relay network if they have been deleted.