Streaming video doesn't need to use I-frames for sync, there's a technique called intra refresh they can use to limit the error. That also helps with the nasty "pumping" artifacts you get on static images.

Some codecs do reorder frames for efficiency though (H.264 can be 10 frames out of order but realistically only goes up to 3), which means you have to decode a few before displaying the start frame.