Has no-one come up with a solution yet? Quicktime or Ogg Theora?
I'm thinking
Bink is probably as good a choice as any. I guess it depends on what you consider cross-platform.
If
the Sony PLAYSTATION (R) 3, Sony Playstation Portable (PSP), the Nintendo Wii, the Nintendo DS, the Xbox 360 and the Xbox consoles (using pixel shaders!), the Sony PlayStation 2 console, all versions of 32-bit Windows, Windows 64, the Xbox console, the Nintendo GameCube console, MacOS, MacOS X and GNU/Linux.
are all the platforms you need, you should be just fine.