Si son vídeos para ver descargar y la mayoría de tus usuarios usan windows, entonces los puedes pasar a formato WMV que no necesita codecs porque ya vienen instalados en windows. También puedes convertirlos a MPG pero en formato MPEG-1, que también viene el codec integrado en windows. Para estas conversiones puedes usar (entre otros) el SUPER.
www.mundodivx.com/varios/super.php