I'm a Linux user, and I use WinFF to convert the video to AVI using either "MS Compatible AVI" or "XviD Fullscreen" presets, and setting the dimensions to 320 by 240. If I need subtitles, I either extract them from the original video, find them online, or make my own, then I use mencoder to add them on by running this command:
mencoder video.avi -oac copy -ovc copy -sub subtitles.ssa -vf scale=320:240 -o video_s.avi
I haven't had any problems with these videos in either mplayer of the included media player. I think that both WinFF and mencoder are available for Windows. Normally, a standard AVI file would work, but you should rescale it before playing it because if you don't you may notice that the video may look "checkered" with the included media player.