Hay bastantes formatos de mp4 (valga la redundancia). No sé si te servirá de algo... te puedo recomendar el AVS video converter, es bastante bueno, la versión 4 (para mí la mejor) para pasar a mp4 de PSP específicamente. No tengo mi PSP pirateada, y menos, uso Linux, así que... al menos espero haberte servido para 'descubrir' un programa bastante decente xD
Suerte.