Even if I don't, any inbox chosen to randomly download could have videos.

Good point. Though you can probably use 'blocks' (think like hard-disk blocks) instead of complete mail boxes. You download random blocks that also contain blocks from your mailbox.

You can't just download random blocks until you get your data though, you might never download some blocks. So you need some kind of index of blocks. And your client can't generate that because the server stores all the data. So it's a server-sided index.

If you only download the index for specific users, that's no different than an inbox: if you pull the index for an inbox and don't pull all the associated blocks (including videos), that's obviously not your box.

The other alternative is downloading the entire index for every single block, which sounds even worse than just downloading random complete inboxes with videos. Especially if the blocks are going to be filled with trash inboxes filled with trash data to obfuscate the sender. Even my own blocks would get trash data including videos that I have to download to pretend it's real.

Fountain codes and other tricks might help.

Ie any block could be useful for multiple inboxes and messages. See also how freenet used to do it. https://en.wikipedia.org/wiki/Freenet

Freenet, as a distributed data store, just makes the issue worse. Now I'm expected to host images and videos that other people send. Also a distributed data store doesn't free you from downloading random inboxes either. Someone just needs to to be running enough instances to be able to track and identify you if you're only downloading your inbox.

That's why Tor makes you bounce between multiple nodes, to decrease the chance you get only nodes that belong to a tracker. Actually not sure why I didn't think of Tor as something that already fulfills all those anonymous requirements. It's also an example of the drawbacks of being completely anonymous, that network is extremely slow and will definitely not scale to anything mainstream.