We have bought one of those small mp3 players with video which play "amv"<> semi format.

Dependence on Windows suck, but you can pull few tricks by recoding your various formats into correct resolution before encoding them:

ffmpeg -i source.avi -s 160x120 -r 16 -acodec copy /tmp/test.avi

This way ffmpeg will scale video to superb quality and AVM Transform.exe won't choke on them.