I've attached the example app and the video I have been using to test video playback (videoExample.zip).
I didn't find a way when the video always plays or always fails. Seems to happen more frequently after a fresh device restart and if you play the video quicker after app startup; but wasn't able to verify that.
Tested both with N8 with latest commercial FW 14.002 and C7 with FW 21.006 - happened on both devices and FW versions.
Used Qt 4.7.2 and Qt Mobility 1.1.1 (taken from Qt SDK Beta) on both devices.
Also uploaded a sample video to play, plus recorded videos where I started the app from Qt Creator and you can see the bug. Due to the file size restrictions of the bug reports site, I've uploaded those videos to a wiki - only internal access, sorry: http://wikis.in.nokia.com/pub/TscPresentations/WebHome/VideoBugReport.zip
n8-fail.mp4: Starting video on N8 two times - black screen. Audio was playing fine during this test. Note that I've stripped the recorded audio track from the video file.
c7-fail-works.mp4: First time starting the video on the C7 doesn't start playing at all (also no sound). Second time, playback works fine, including audio and video.
test3.mp4: the surfing sample video that came with some Nokia phone.