I had exactly the same problem. The game seems to run fine under XP, but a number of videos don't show, just a black square, though audio works. Installing Indeo codecs didn't work. I never managed to solve the problem. I even tried it again on a fresh installation of XP, but that didn't make a difference, though it runs fine on windows 98.
I've already posted a question about this in this forum, http://www.vogons.org/viewtopic.php?t=6305
, dated 2004-8-28, with title No movies running Starship Titanic on Windows XP, but I never received a reply.
Just to make sure there are no misunderstandings, the problem wasn't finding the required codecs! I found and installed them, but that didn't work.
I'm using SP2 as well. Or maybe it's the video card, it's an ATI 9600 Pro.