Not only has Sony excelled recently in Rootkit DRM technology, they've also managed to create Yet Another Video Format solely for the PlayStationPortable device. Yep, you can't play ordinary MPEG-4 files on PSP.
The 2.0 firmware does support MPEG-4 AVC (H.264), which provides very high quality in low bitrates. But you need to package the video stream in a special, Sony-only video format and directory structure. And of course, you can buy software to do this.
Since I needed this at work, I just purchased Nero 7 Premium Edition, which promises to do PSP video with Nero Recode. It does, except that it's apparently MPEG-4 Simple Profile only (no AVC), so quality sucks and the video doesn't even scale to fullscreen.
It turns out there is a free alternative called PSP Video 9 that supports MPEG-4 AVC. In fact, it works like a charm. Very crisp image quality and fullscreen video. So there.