I was part of a team that designed and implemented a P2P UDP based video streaming protocol, that receives chunks of a stream simultaneously from up to hundreds of peers. It wasn't a "big problem" per se - I worked on seemingly harder problems before and since - but this one was really hard to get right, it was a very non deterministic beast that was extremely hard to test. I remember lots of times that I secretly felt like we would never get this thing working as well as we wanted, but in the end we did.
I left this company long ago but they appear to be going strong still. http://www.giraffic.com/ . I'm sure they improved on that work a lot since then.
Wow, it was so long ago, I don't remember the exact data structures, but I'm pretty sure it wasn't a skiplist.
If you've already asked, one cool part of that technology is that the order of received packets is not important to assemble the stream. Basically every 1 second of video is reassembled without importance to the order of packets received. You need N packets to assemble a "data frame", IIRC pending incomplete data frames were stored in a simple hash table, but honestly it was so long ago I don't remember.
I left this company long ago but they appear to be going strong still. http://www.giraffic.com/ . I'm sure they improved on that work a lot since then.