h.264 is deffinitely preferable to DivX/XviD given it's high level of compression and superior quality. It works with Quicktime7 which means it wouldn't be difficult to code up for OS X support (we could decode the video frames directly to OpenGL for instance). Windows would just need a compatible DirectShow filter (though we'd still have to deal with the piece-of-**** DShow code). Linux would still have to use ffmpeg which gives us the legal issues again on that side, unless we never distribute binaries that are linked to ffmpeg, and never use ffmpeg libs which contain the GPLd code (liba52 and libpostproc). The main problem with all of that is it's 3 totally different portions of code which have to be written/rewritten and maintained, each with their own quirks.
The only source code that I know for x264 is GPL, which we can't use, so I don't know of a way to just have that one codec built right into the game source (like MVE is). That means that we would have to rely on an external system to decode movies and that's where we are running into issues with the current code.
As fizz points out, Interplay is unlikely to do anything at this point. MVE is antiquated and totally unsuited to current games, much less future ones. Plus the source code and format docs for MVE have been publicly available since at least early-2002/late-2001.

isn't going to do anything about us using MVEs, since it's not their tech, and Interplay is bankrupt, the fate of their IP is unknown. Suing over this isn't going to pay off for them since there is no way to get a good monetary settlement out of it. Off the top of my head I can think of at least a dozen open source projects which have MVE support (and have had it for years) and Interplay has done absolutely nothing about it. File size and color quality is a problem I agree, but it's something that we can deal with 100% in the game code. We don't have to rely on an external source to decode a/v. That also gives us 100% control to optimize and bug-fix the movie player.
There is just going to be no win-win here. MVE suffers from hi-color dumbness and large file size. Anything-else is going to greatly increase support issues and require much greater coder work to not only write the code, but also to keep it working. Downloading issues are a problem, but many people already have the game which means they already have MVEs. MVEs (since they use CFILE to load and use) can easily be used off of a CD or DVD and you can save the HD space. If

decides to get serious about protecting it's copyrights on the game data then everyone currently distributing the game over the internet is going to have trouble on their hands at which point downloading no longer becomes an issue. With every possibility you can run off a page of negatives about it.