If they don't work in the game after you encoded them again (assuming you have a working encoder at all -- game formats are tricky things here and encoders are rare) then either you used the wrong encoding settings (depending upon the format could be anything from basic resolution settings to something far more complex like the game/xbox not supporting a particular setting that has become standard/popular in more recent years, you could try to figure it out but more likely just set whatever profile settings you have to the most restrictive. It will send the size higher but it is not like space is much of an issue) or your encoder did not also replicate any headers or container aspects that the original file has and it needs*.
*take the original and encode it back again matching every setting you can, as it is likely a lossy process a simple binary compare will likely not yield much but might tell you something there.
Alternatively softsubbing, or the adding of a softsub option, should not be the worst for something as powerful as the original xbox (people did it on the DS and PSP so original xbox should be no problem).