What if all inboxes were public, but only decryptable by the recipient? Recipient can then poll for new messages.
There might be problems with the proposed model, but they aren't the problems you suggested.
(As an individual, you wouldn't want to download just your own inbox. But to obfuscate, you can download a random subset of inboxes that often-enough includes your own.)
And if you want to be anonymous you can't filter by the last message you've received, so every time you pull your inbox, you're getting the last X time in messages. So if I have multiple active group chats, that would really start to add up.
Videos and images like every other messaging service would have to be anonymized the same way. Even 10x noise polling for a 10MB video would be too much data on phones and probably not enough to anonymous. How about obfuscating the sender? Would a sender be uploading 10x trash, not just text but also video, messages in every inbox?
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.
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
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.
Some Bitcoin SPV clients have tried solving an almost equivalent problem, but the obvious approach does not work for various subtle reasons: https://eprint.iacr.org/2014/763.pdf
Check out alt.cryptography (I think) if you can.