I've encountered similar situations. A bunch of my home videos (2~3 minutes) were converted to .mp4 with the "better" settings (640kbps video, 400x240, 27 fps, 96kbps audio). They played fine on desktop PC and N810/OS2008/Media Player. However some of those .mp4 videos are having the same stopping problem on Motorola phones (krzr and rizr). I'll try the lower settings.

[edit] Just tried lower settings, same problem.