ニコニコ動画でよくつかわれている、On2VP6（flv4) は CorePlayer/TCPMP ともに対応できていません。
...まぁ、大人の事情というか、利権争いというか、WMPだってMSがっつりだし、QuickTime だって Apple がっつりだし、そんなところです。
でもニコ動画をモバイルで、「なるべく簡単に見たい」という方は、Craving Explorer などを使ってみてはどうでしょう。
ダウンロードから返還まで驚くくらい簡単に処理できます。PSP用とか、iPod用の設定があるのもうれしいですね。
Windows Mobile 用ならば、avi なり flvなりにしておけば、OKでしょう。MP4は再生負荷が高いのでお勧めしません。mpeg や avi はファイルサイズが大きいので、flvならちょうどいいかもしれませんね。