If you are on a 1.5 PSP like me, I suggest you cease to use MP4 video playback and change to PMP like I have done. Unlike the MP4 playback, it allows full resolution of 480x272 and it seems to be better quality at the same bitrate.
Download
AviToPMP which converts the original video to pmp. It seems to support every type of video file I have found, including MP4 and VOB. It allows VBR on both video and audio and is basically a front end for Mencoder.
To play the movie back on the PSP use
PMP Mod V2.0. This software will only work on a 1.5 PSP though. It is superb software with much better controls than the inbuilt MP4 player.