Video encoding during publish

A .story file with 4 mp4 videos.  Usually, when I publish, the entire course publishes in about 30 seconds.

Occasionally, the publish dialog takes much longer and shows "encoding video ..." for each video.

Strange thing though, deleting the temp folder, closing Storyline and relaunching seems to have no bearing on whether we get the "Encoding mp4 video".

So... sometimes the course publishes in 30 seconds, other times 5 minutes, and it all boils down to the "Encoding video" surprise when I publish.

Any ideas?

Sam