Personally I would put mp4 at the end of the title. eg: Billy's video clip - mp4 or the beebles - mp4
You could put .mp4 at the end of it but that may make the search too specific for the earlier title. Just my thoughts.
I can't remember if this link is any help for your purpose or not, but it roughly discusses similar techniques for searching: Cant search well help