Join video streams on keyframes
For keyframe based video (as opposed to rolling intra refresh) clients can't display output (correctly at least) until they hit a keyframe.
So it would be useful if streams started on keyframes. There are a couple options for this.
If latency is unimportant and the server doesn't mind the memory usage it could buffer the span between keyframes and when a client attaches attach them back at the last keyframe. This would be like a keyframe adaptive preburst.
Alternatively, if latency matters more the server could reencode. The best way to do this would be to constantly reencode with a very short keyframe interval (e.g. 1-12 frames) and play this out to new clients until a real keyframe comes. Optionally a 'loading' spinner could be displayed to avoid confusion from the low quality during this span. This is O(N) in the number of streams and O(1) in the number of users.
For some formats it would be possible to do some format specific smartness. E.g. in theora You could retransmit the prior keyframe timestamped as NOW-2, then reencode the prior frame (using all intra blocks at high quality) as NOW-1. Then splice in the stream. There will be some corruption until the next keyframe but it should be very minor. Unfortunately it would cause a jump in the visible output because the first frame is an old one.
Alternatively, alternatively, a pre-encoded short GOP "loading" video stream could be sent to users before the first new keyframe. Audio could be spliced in instantly however. This would avoid encoding in the icecast server.