I'm not a fan of timestamps for all of the reasons you describe here @Aljoscha.
I would be really keen for some kind of causal public feed ordering. I think this was discussed recently. If there was a way to query to query the indexes in a causal order, and only use timestamps if available as a display hint, I think things would be much more solid.
Threads make this pretty easy since you can acknowledge other posts as branches, but something I've been thinking about is tagging root posts with similar branches. Maybe the hashes of a few other feeds' latest messages as a reference point. I haven't had a chance to catch up on these discussions, so apologies if I'm repeating something that's already been talked about. And if there was no available reference for a given post, you'd fall back to sync time compared to other posts, and update the order later if more info was discovered.
Anyway, you have my support in this matter @Aljoscha.