La cosa migliore che io ho provato è il formato FLV (FlashVideo) ti permette di non avere lo stesso video in diversi formati cosa che riempie il server...che poi con quei formati non sarebbe in streaming, ma in progressive download.

Ma grazie al formato FLV puoi avere una sorta di streaming con un solo formato perchè il player è lo stesso flashplayer!!

Questo metodo lo usa anche Google Video su:
http://video.google.com

Per info sull'FLV:
http://pro.html.it/articoli/id_660/idcat_30/pro.html