According to Major Nelson, the backwards compatibility for the XBox 360 will not require re-compilation, nor will it require purchasing a new version of the games. Apparently the goal is that every XBox game will work on XBox 360.
What this says to me is that backwards compatibility will be implemented through emulation. Now, they may use pre-compiled binaries to complement this, however that could be more complicated than useful. I think that they will get the emulator working with the top titles (including Halo and Halo 2), and endeavour to get it working with as many other titles also. The games that bypass APIs and go direct to hardware will be the ones that cause the problems, and they may end up being impossible to emulate. In these cases, pre-compiled binaries may be the answer.
In the end of the day, whatever method they use, it means that you will be able to play Halo and Halo 2 on the XBox 360, without buying a new version of the game.