Issue playing back Captivate 9 mp4 files in Windows Media Player

Hi everyone, have been looking on the forums and have tried a few things but can't seem to get this resolved, so looking to see if anyone has managed to fix this themselves.

I have been making self-help videos for 2 different companies, my own and another that we are soon to merge with. I have been using Captivate 9 on windows 8.1 to make the videos, then exporting them as .mp4s to host on their CMS and then create links to the videos for going on their intranet.

So far, if I play the video in VLC on the external company's laptop (they have sent me over their laptop which I can remotely connect to their network) then it works perfectly and I can see and hear the video in perfect clarity. If I play that exact same file through Windows Media Player on the same laptop, all I get is a thumbnail of the first screen in the video, and the audio plays along while this is displayed.

When I test the files on my own laptop they play fine in both VLC and WMP.

So we reckon there's an issue with the codec on the external company's side...

What I am wondering is, is there a way we can publish these mp4s so that they play in WMP, without having to install an encoder on everyone's machines?

I have already tried publishing the mp4 as Youtube Widescreen HD as suggested here but this did not resolve the issue. Just wondering if there's anything else I can try.

Thanks in advance for any suggestions.