That's fine, specifically because no one really follows more than 400 people. When they have more than that it's because they're interested in some "trends" more than the actual specific people, so relay feeds with whatever algorithms would be a much better choice.

Eventually users will have to learn too, they can't just expect things to work the best way for them without no work (and it can't be argued that such approach works on centralized platforms, it doesn't).

(Still, I think normal outbox will work fine with any number of users as long as you have a local database that is proportionally big and a syncing process that is slow and patient.)