After lots of troubleshooting and testing we finally discovered the issue and the solution. The web application that hosts our Asia Pacific intranet had its Browser File Handling settings set to Permissive, while the other servers and web applications had it set to strict. After changing that, the video worked everywhere.
Note: This change affects not only the video files, but of course all files in your environment (PDF, Office, …). So before changing it, make sure that it doesn’t introduce any unwanted behaviour
Here are the steps to get there:
Open Central Admininistration -> Go to Manage web applications -> Select the corresponding web application and select General Settings from the Ribbon -> select General Settings again -> Change Browser File Handling from Strict to Permissive