How much time and effort goes into getting Theora support in the game depends on support from the mods since they are the ones that will have to deal with the transition from AVI.
The only mods that use AVI movies that are actually
released are Lightning Marshall and Transcend, AFAIK. Everything else is still in development. For LM and Transcend, we'd have to get in touch with the original developers, but for the rest, it's quite likely they still have the raw movies around. If we were to say, in a sticky thread or something, "Here are the options for encoding movies, and here are the codecs to use", then the changeover should be doable without much difficulty IMHO.