From personal experience FLV's are the best way to handle video. NetFlicks uses this, likewise with LOVE Movies. When I streamed a video clip a while back (pre YouTube days) I used flash to do this, worked like a charm.
Try using Adobe AfterEffects and then expert it as a FLV, if it works through there. You can also use Adobe Flash, but from experience, AE performs a better task on rendering as it's geared towards video playback. You will need a high powered rendering computer. When I did animation a couples of years ago I use to have a workstation with 32GB of RAM. RAM is the key to rendering.