There still seems to be some confusion here:
mpeg4 is an mpeg 'wrapper'. mpeg4 may contain several different codecs including Xvid, h.264, and DiVX. My 'guess' is that Sony (being as proprietary as they are) have a specific codec that your phone can play, and you must use their software to encode to that codec (or find out what it is and find an application that allows the option to encode using that codec). To further the problem, when the PSP was first released there was some talk about file naming structure, this may also be the case with your phone. It may need a special nomenclature for the filename to even "see" the file.
If you have a video that can play on the phone, throw it on your computer. Use mplayer to identify the video type and codec used, and then try encoding your video with similar parameters.