Right, I had the same problem you had and I found out that only the first no-cd patch for 1.1.0605 (no-cd #1) allows the videos to play. It is rather big (it's the full executable) but it's the only one on GCW that plays the videos for me.
Morrowind 1.1.0605 no-cd #1
Copy this one over your existing executable and tell me if it works for you.