Starman, you're correct in that I wasn't talking about the cutscenes. I meant the in-game captures. Thanks for clearing up about the 640x480 not being reworked. I highly suggest that somewhere in the installer program you make this fact very clear.
Btw, 30fps is plenty for distribution video. I edit my videos in either 23.96 fps or 29.97 frames per second because as far as videos go, that's pretty standard. Your typical animated movie has been shown in theatres in 23.96 fps then telecined to 29.97 fps for the dvd release. The other notable reason for this is that even using a lossy codec like div-x or xvid that works off of key frames and interpolation, the computer would still have to deal with that many more frames and the filesize would be that much larger.
In general, you just need to remember that gaming and video are almost two entirely different worlds as far as visuals go. Games throw away frames once they've been shown so that higher framerates make sense and look nice. In fact, higher than 50fps and you should be looking at ways of making the game prettier so that you are left with a pleasant frame rate of 30-50 fps while making the most of your machine's memory.
In video, you want a consistant frame rate of either 23.96 or 29.97 fps. Otherwise you'll end up with timing issues when you compress the audio.
There's a great guide to working with video and audio
here, although it deals specifically with working with dvd rips and anime. Taught me everything I know about working with video and has links to some very impressive open-source tools.
There's a section dedicated to making your video files more compressible and at the same time prettier (by way of smoothing and sharpening filters) that you might want to have a look at especially if you're still working on your cutscenes.
Edit: I just reread your post and those filesizes for the cutscenese seem almost too reasonable. How did you get them so small?