Mp4 video - erratic behaviour

We have some problems with cinematic sequences in our game - we have imported mp4 videos and most of the people see them fine. But for some, all they see is a black screen and the game continues after the sequence, but for some, starting the video crashes the game.
Is there some recommendation for the most suitable codec that will play without a hitch?