Are you encoding to the proper resolution for your player? Have you verified that your player is indeed 4GB? How are all your videos starting in the same place?
I use AviSynth with Virtual Dub to pre process my videos before converting to AMV. I get very smooth playback and small file sizes. Sounds like your problem is with the player more than the AMV's themselves. Try downloading some of the sample videos in the download section and try those. Or if you like I can convert a test video for you in the resolution you need for your player. Hope this helps.
