ニコエンコ以外のソフトは試してみた？
おれはニコニコやyoutubeを落とした後は、Freemake Video ConverterというフリーソフトでFLVからMP4に
エンコしてからEDIUSのbinに登録している。

とりあえず、真空波動研とか使ってコーデックを確認してみるところからしてみてはいかが？