Videos em j2me

Sim, é possível rodar vídeos na sua aplicação sem problemas.
Não, acredito que não seja possível você instalar codecs no celular, ou baixá-los pela sua aplicação, a não ser que você crie o seu codec e que execute-o através de arquivos de configuração, mas não sei até que ponto isso é viável.
Depende muito de fabricante, pois cada uma, implementa a capacidade para cada celular visualizar os vídeos. A Nokia tem feito um grande esforço no sentido de padronizar a transmissão de vídeos, usando o seu formato 3GP, que é o menor de todos e com uma qualidade aceitável.
Porém nem todos os outros fabricantes implementam o 3gp e você terá muita variação.
Resumindo, a sua aplicação, deverá antes de rodar reconhecer qual é o celular, e qual(is) são os tipos de vídeos que rodam nele.

Desenvolvemos um sistema que transmite vídeos e passamos por esse problema. Aliás nem apenas vídeo. O mesmo problema ocorre com imagens, sendo que nem todos os celulares conseguem ler, gifs, jpgs, png, etc.

Abraço

Nem todos os celulares suportam isso, mas com MMAPI você consegue tocar um vídeo facilmente, mas ou menos como o código abaixo:

Player p; VideoControl vc; try { p = Manager.createPlayer("http://server/somemovie.mpg"); p.realize(); // get video control vc = (VideoControl) p.getControl("VideoControl"); .... p.start(); } catch(IOException ioe) { } catch(MediaException me) { } ...

Nesse link fala mais sobre mmapi:
http://developers.sun.com/techtopics/mobility/midp/articles/mmapioverview/

A maioria dos celulares que suportam vídeo é em MPEG-4.