Its a bit curious. When you use .mp4 the server has to convert it and that can take some time. And is generally less reliable because of that. It would usually be ok for a minute or two, so possibly the server is congested.
Just to be sure make sure your file upload limits are adequate. (Thats a bit of a long shot, but worth checking). Othewise.
i) If you can live with .flv videos, then don't use .mp4. This will be more reliable
ii) Set up FFMPEG to run on your Moodle server and handle file conversions locally.
(there is a document here on the forum somwhere on how to do that. Or I can repost it.)
iii) Use PoodLL3 on Moodle 3.1. and HTML5 video recording with Google Chrome and Mozilla Firefox. That has a different conversion system and no Red5 bottleneck.