H.264 encoded videos carry their metadata – duration, frame rate etc. – in the so called “moov atom”.
By default encoding programs will insert the moov atom at the end of the video file which is suitable for playback of a local file in a desktop program. However, any kind of progressive download requires the metadata to be available right away for immediate playback. Otherwise the player has to wait for the entire video to be downloaded before playback starts.
Make sure to select an option in your transcoding program which puts the moov atom at the beginning of the file!
I would recommend using QTIndexSwapper as it is built on adobeair if your videos will not play straight away and you have to wait till fully loaded then this is your issue.