i just got a motorola v710 and it can play movie files. they have to be in .3gp or .3g2 format, so i use Nokia Multimedia Converter 2.0 (you have to sign up to nokia's forums to get a license) to convert any file into the correct format. it really shrinks the vids a ton. example, i took a 330mb skateboard video (play time approx 1hr 20mins) and it shrunk it down to about 20mb. the quality is still pretty good, and the audio plays fine thru my v710's speakerphone. i've got a 128mb transflash card for my phone, so i can store quite a bit of content. probably about 6hours of tv shows or full length movies if i wanted.
windows media player will also play .3gp and .3g2 files.