Shamo42 has perfected a method of encoding video for PSP that produces a much sharper image. We gave it a test, and the results are impressive :

The drawback is that it takes twice as long, since the video has to be re-encoded using VirtualDubMod.