[vetinari]

(At least Threema does it this way): Server doesn't really store the messages long term; only until the receiver picks it up. With just two devices - sender and receiver - you have a guarantee that once the single receiver picks it up, there's none else to do the same and can be safely dropped.