I experienced the following on an old laptop running Windows XP (SP3) on a very high speed connection.
While using Explorer 8, the videos displayed OK in the NN online viewer after clicking on the the play triangle button. Most started right away as before, some took a few seconds to start up.
When I tried using the MP4 link, Windows Media Player 10 popped up and said could not play the file type. Updated to Windows Media Player 11 and it also said could not play the file type. Did a bit of Internet searching that suggested that it might be possible to download some non Microsoft codecs that would enable Windows Media Player to play mp4 videos. Having had bad experiences in the past with non MS codecs I decided to download and install the free VLC Media Player instead.
Installed the free VLC Media Player and restarted the laptop. Started up Explorer 8 again. Videos started and displayed OK as before when I just clicked on the triangle play button in the NN online viewer. Now though, if I click on the MP4 link, a dialog appears asking if I want to open or save the video. If I select the open option, the video appears to be downloaded in its entirety into my default VLC folder (saved as a file ending in a ".mpg" extension) and then automatically starts playing in a VLC Media Player window. If I select the save option, a save dialog appears showing the default VLC folder. Clicking OK then downloads the video as before but it does not then start to play automatically. In order to see the video after using the save option, I must find the video file, and then double click on it, which starts VLC and shows the video.
Not making any suggestions ... just reporting how the new videos work for me on an old system.