First of all, I suggest to use 3gp file format for video. Tool for converting 3gp files can be found from here. There's also Video in Nokia phones document available. Encapsulating an MMS message with video clip is the same as with any other content, just use video/3gpp MIME type.
Streaming is supported in Nokia 3650 which uses the RealOne player.